题目链接 题意：问长度为n，每个位置由且仅有‘H’和'T'组成的序列中，至少有连续k个‘H’出现的方案数。 思路：不会做，参考了题解 不过没有完全搞懂。 根据题解，正面考虑比较麻烦，所以反面考虑。[j] dp[i][j]表示长度为i，前面最后连续的‘H’的个数不超过j个的方案数。 考虑转移方程为： 总的情况为：dp[i][j] = dp[i-1][j] * 2; 但是其中有多考虑的情况，就是第i位是'H'，且i位之前的最后j个位置都是'H'（即从i-j位到第i-1位都是‘H’，此时第i-j-1位必然是'T'） 有i个硬币时，如果i 如果i > j + 1，dp[ i ] [ j ] = dp [ i - 1 ] [ j ] * …

题目链接 题意：n个数，分成若干段，每段的代价为 ，求最小代价。 思路：dp。 状态方程很显然个鬼。。。 dp[i] 表示处理完前面i个数的最小代价。 dp[0] = 0 ; dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。 这复杂度是n^2的。。。然而n最大5E5.....boom.... 斜率优化登场！ 这篇博客讲得非常好 我们假设k两边移项一下，得到：(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我们把dp[j]-num[j]^2看做是yj， …

hdu 4283题目链接 题意：有N个人按顺序排成一排上台表演，每个都有一个num[]值，若在他是第k个上场的人，则会有num[]*(k-1)的unhappiness。台下有一个黑屋（stack），对每一个人，可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。 思路： 我想对了的： 无。状态设计就错了。。。转移方程也就不可能对。。。 错的一塌糊涂。。。嗯。。基础题。。完全不会2333 参考题解：参考博客1 参考博客2 /* *********************************************** Author :111qqz Created Time …

poj 3661题目链接 题意：锻炼，一共n分钟，每分钟可以选择跑步或者休息，第i分钟跑步可以跑d[i]米，并增加一点疲劳度，如果选择休息，那么每分钟减少1点疲劳值。一旦开始休息，必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0，否则之后会感觉身体被掏空。问n分钟最远多多远。 思路： 我能想到的： * dp[i][j]表示第i分钟疲劳度为j的时候能跑的最远距离 * 初始化dp为0. * 最后的答案为dp[n][0] * 如果第i分钟跑步，转移方程为dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]); 我想错了的： * 休息的时候的转移方程应该是第i天刚好** …

poj 1651题目链接 题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。 思路：能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T 参考了几篇题解，思路大概是，枚举最后剩下的那个数。 **对于一个区间(l, r),如果最后删除的是k位置的数的话，将得到a[l]*a[k]*a[r]分，而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是** DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r]; 以及。。。初始化又想错了。。。 要注意。。初始 …

poj 3280 题目链接 题意：一个字符串，给出添加一个字符或者删掉该字符的花费，问最小的话费使得字符串变成回文串。 思路：dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。 这个可以想到。。dp[i][j] = dp[i+1][j-1] (a[i]==a[j])这个也可以想到。。。 增加和删除是等价的，所以取小的那个代价就行。。这个我也想到了。。 然后转移的地方没有特别明白。。。 和之前的找到一个划分的点k不同的是。。。 如果不等于。。 那么 , dp[i][j] = min(dp[i][j],dp[i+1][j]+cost[a[i]]); dp[i][j] = …

light oj 1422 题目链接 题意： 按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。 思路：没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。 参考了10多篇题解。。。终于懂了一点。。 参考博客1 参考博客2 参考博客3 参考博客4 **当a[i]和a[j]相等的时候 dp[i][j]=dp[i][j-1] 嗯，就这一个转移。然后就是区间dp的固定写法了。** 这句话让我恍然大悟。。。难道。。都是套路？ dp[i][j]表示的是[i,j]之间最少需要 …

poj 1141题目链接 题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。 思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。 参考了这篇题解：参考题解 记录路径的思路是。。。记录转移的点。。。 cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。 cut[i][j] …

poj2955题目链接 题意：给出若干括号，问最大匹配数是多少。 思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序? 循环次序？我一点思路都没有。。。。。 人生中第一道区间dp(这话我都说了不知道多少次了。。。每次都学不会。。。。sad) 我的dp水平和其他部分的水平还真是不匹配。。。 看了题解。。。自己写（抄）了一遍。。还是觉得好玄学。。。 细节见代码。 /* *********************************************** Author :111qqz Created Time …

1652: [Usaco2006 Feb]Treats for the Cows Time Limit: 5 Sec Memory Limit: 64 MB Submit: 290 Solved: 226 [Submit][Status][Discuss] Description FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he …