hdu2018题目链接 题意:第1年有1头奶牛，每年生一头奶牛，新生的奶牛从生下来的第四年（包括生下来那年）也开始每年一头奶牛。 问第n年有多少头奶牛。 思路：最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4) 递推代码： /* *********************************************** Author :111qqz Created Time :2016年07月27日 星期三 13时19分17秒 File Name :code/hdu/2018.cpp …

hdu2084题目链接 题意：dp入门题。。。数字三角形。。 思路： 昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse... 为什么自底向上呢。。。 初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。 需要特别强调的是。。处于某个子问题的时候。。。其他部分就好像不存在一样。。。 每一个点只能向下或者向右下两条路可走。。。 那么对于这一点的最大值。。。一定是取后来可走的两点的最大值加上自身。。。 /* *********************************************** Author :111qqz Created Time :2016年07月27日 …

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]之间最少需要 …

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

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 504 Solved: 265 [Submit][Status][Discuss] Description The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 451 Solved: 226 [Submit][Status][Discuss] Description 考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图： . . B x . . x x A . . . . x . . x . . . . . x . . 贝茜发现自己恰好在点A处，她想去B处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管 …