传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1158 不知道为啥，这道DP把我脑袋快转晕了，有个地方想到了，可就是转不过去，真晕菜。 不过历经2小时，还是写出来了，这花的时间，真囧。。。。 分析： DP，这一题数据范围没给出，不严谨。经测试，公认数量开105就行了，工资我现开始开0xffff，然后WA了，接着开了0x3ffffff，就AC了。 数组dp[i][j]表示第i个月员工数为j的总花费。 这题逐层(月)考虑，在上一层顺序遍历每一个dp[i-1][j] != INF的： 1.如果上一层(月)(即j)比本层(月)要求的人数(即man[i])少，则只需要雇佣相差的人数 2.如果上一层比本层要求人数多，则在man[i]和j之间，dp各个情况就行。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2151 先开始用的BFS，结果爆栈了，然后换成DP~~~ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 [...]
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1069 DP~~~ 感觉有点类似二维的LIS。 好久没做题了，发现自己变水了很多，今天中午到的家，大概住20天~1个月吧，现在HDOJ的AC量是320，希望返校前能达到500，当然，如果仅此任务还不算很难，可是还有其他很多要学的，所以尽力吧。 代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [...]
利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。不过经常还是用在DP题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，前面的解往往舍弃！所以用滚动数组可以说是很有必要的。 滚动数组 举个简单的例子： 1 2 3 4 5 6 int i, d[100]; d[0] = 1; d[1] = 1; for (i = 2; i < 100; i++) d[i] = d[i – 1] + d[i – 2]; printf("%d", d[99]); 上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]; 为了节约空间用滚动数组的做法： 1 2 3 4 5 6 int d[3]; d[0] = 1; d[1] [...]
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1267 分析，这题其实是H和D的组合排列问题，只不过要考虑期间累计的H和D的数量关系。 用DP来做，可以推导出： dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[][]前一个表示H的数量，后一个表示D的数量。 分上面那种情况是因为最后一个必然是H或者D，而此时可以考虑把新加的一个放在最后，因为假如加的是H，如果加在[i-1][j]中加入H，则最后一个依然是H或D，此时如果成立，那么依然属于[i-1][j]或[i][j-1]的情况。 所以推导出此递推关系。 以下是AC代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> #include <string> #include <algorithm> using namespace std; __int64 dp[22][22];// 前面是H，后面是D int main() { dp[1][1] = [...]