大概是：整数划分||DP||母函数||递推
整数划分问题整数划分是一个经典的问题。Input每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)Output对于每组输入，请输出六行。 第一行： 将n划分成若干正整数之和的划分数。 第二行： 将...
递推DP Codeforces Round #260 (Div. 1) A. Boredom
题目传送门 /* DP：从1到最大值，dp[i][1/0] 选或不选，递推更新最大值 */ #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> u...
hdu 1284 钱币兑换问题 (递推 || DP || 母函数)
钱币兑换问题Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5069 Accepted Submission(s): 2868Prob...
洛谷 1192：台阶问题（递推，DP）
题目描述有 N 级的台阶，你一开始在底部，每次可以向上迈最多 K 级台阶（最少 1 级），问到达第 N 级台阶有多少种不同方式。输入输出格式输入格式：两个正整数N，K。输出格式：一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod 100003 后的结果。输入输出样例输入样例#1：...
【DP】一道递推题。。。
Bob想要构造一张由n个节点构成的图。构造的过程由两步组成：首先Bob会取出n个孤立的点，并把它们从1到n编号，然后对每个节点用一种颜色染色，Bob一共可以使用K种不同的颜色。接下来Bob会在这张图中加入一些有向边，对于每一个编号范围在[2，n]的节点i，Bob有可能选择一个节点j满足j <...
NOIP模拟题 [递推][优化][dp][线段树][离散]
稳啊稳啊。对拍大法好。 不过最开始看题的时候要记住评估一下正解难度和暴力难度，T3明明可以搞60分的，可惜了。 还有就是，写程序之前一定要想清楚！处理好特殊情况，确保算法在实现过程中的正确性！对拍出错再来改代价太大！T1: 题意： 对一个给定字符串进行多次复制黏贴操作，求最后得到字符串的前n位，若字...
Shell Necklace (dp递推改cdq分治 + fft)
首先读出题意，然后发现这是一道DP，我们可以获得递推式为然后就知道，不行啊，时间复杂度为O(n2),然后又可以根据递推式看出这里面可以拆解成多项式乘法，但是即使用了fft，我们还需要做n次多项式乘法，时间复杂度又变成O(n2 * log n)，显然不可以。然后又利用c分治思维吧问题进行拆分问题但是，...
hdu1078 dp(递推)+搜索
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1078题意：老鼠从(1.1)点出发，每次最多只能走K步，而且下一步走的位置的值必须必当前值大。求这些位置和的最大值。思路：用搜索逐步找每个点能到达的最大值，也是子最优解到整体的最优解，dp思想...
[NOI2017]泳池——概率DP+线性递推
[NOI2017]泳池实在没有思路啊~~~luogu题解1.差分，转化成至多k的概率减去至多k-1的概率。这样就不用记录“有没有出现k”这个信息了2.n是1e9，感觉要递推然后利用数列的加速技巧f[n]表示宽度为n的值，然后枚举最后一个连续高度至少为1的块，dp数组辅助神仙dp：dp[i][j]表示...
NOIP模拟题 [递推][DP][搜索]
T1: 题意： 要求将1-n的数排成两列，使得两列数的个数相等且都递增，还要求其中一列比另一列对应位置上的数大。 分析： 两个方法： 1.先写个暴力打表找规律，因为反正也要写对拍。 2.分析一下： 如果我们把1-n看做一个n位二进制数，用0表示在第一排，1表示在第二排，则前面的0数...
POJ 2441 Arrange the Bulls 状态压缩递推简单题 （状态压缩DP）
推荐网址，下面是别人的解题报告：http://www.cnblogs.com/chasetheexcellence/archive/2012/04/16/poj2441.html里面有状态压缩论文的链接，可以看看。该解题报告中用的是二维数组，但是很显然的是，递推式中的下一行只与上一行有关，类似于最长...
递推DP URAL 1017 Staircases
题目传送门 /* 题意：给n块砖头，问能组成多少个楼梯，楼梯至少两层，且每层至少一块砖头，层与层之间数目不能相等！ 递推DP：dp[i][j] 表示总共i块砖头，最后一列的砖头数是j块的方案数 状态转移方程：dp[i][j] += dp[i-j][k] 表示最...
递推DP URAL 1353 Milliard Vasya's Function
题目传送门 /* 题意：1~1e9的数字里，各个位数数字相加和为s的个数 递推DP：dp[i][j] 表示i位数字，当前数字和为j的个数 状态转移方程：dp[i][j] += dp[i-1][j-k]，为了不出现负数 改为：dp...
递推DP URAL 1119 Metro
题目传送门 /* 题意：已知起点(1,1)，终点(n,m)；从一个点水平或垂直走到相邻的点距离+1，还有k个抄近道的对角线+sqrt (2.0)； 递推DP：仿照JayYe，处理的很巧妙，学习:) 好像还要滚动数组，不会，以后再补 */ #include <cstdio...
九度 1552 座位问题(递推DP)
题目描述：计算机学院的男生和女生共n个人要坐成一排玩游戏，因为计算机的女生都非常害羞，男生又很主动，所以活动的组织者要求在任何时候，一个女生的左边或者右边至少有一个女生，即每个女生均不会只与男生相邻。现在活动的组织者想知道，共有多少种可选的座位方案。例如当n为4时，共有女女女女, 女女女男, 男女女...
递推DP URAL 1031 Railway Tickets
题目传送门 /* 简单递推DP：读题烦！在区间内的都更新一遍，dp[]初始化INF 注意：s1与s2大小不一定，坑！ 详细解释：http://blog.csdn.net/kk303/article/details/6847948 */ #include <cstdio&...
递推DP URAL 1167 Bicolored Horses
题目传送门 题意：k个马棚，n条马，黑马1， 白马0，每个马棚unhappy指数：黑马数*白马数，问最小的unhappy值是多少分析：dp[i][j] 表示第i个马棚放j只马的最小unhappy值，状态转移方程：dp[i][j] = min (dp[i][j], dp[i-1][k-1] + cur...
递推DP URAL 1225 Flags
题目传送门 /* 1 r; 2 b; 3 w 2不能在最前面，所以dp[1] = 2; dp[2] = 2: 13 or 31 dp[i] = dp[i-1] + dp[i-2]; 只加1或3时，总数dp[i-1]; 只加12或32时，总数dp[i-2];...
【CF607B】Zuma——区间dp（记忆化搜索/递推）
以下是从中文翻译成人话的题面：给定一个长度小于等于500的序列，每个数字代表一个颜色，每次可以消掉一个回文串，问最多消几次可以消完？（7.16）这个题从洛谷pend回来以后显示有103个测试点（满屏的AC好爽……上午考试的时候这个题直接用马拉车暴力贪心骗了十五分。然而每次消掉一个最长的回文串并不一定...
UVa 926【简单dp，递推】
UVa 926题意：给定N*N的街道图和起始点，有些街道不能走，问从起点到终点有多少种走法。很基础的dp、递推，但是有两个地方需要注意，在标记当前点某个方向不能走时，也要同时标记对应方向上的对应点。另一点就是要开long long存。要是不考虑障碍的话，按组合数算从(1,1)走到(n,n)需要2*n...