DP

hdu 2670 Girl Love Value      摘要: dp
按损耗值由大到小排序  阅读全文
posted @ 2009-05-17 21:28 Going 阅读(289) | 评论 (0)  编辑
hdu 2372 El Dorado
posted @ 2009-05-14 20:24 Going 阅读(284) | 评论 (1)  编辑
zju 1520 Duty Free Shop      摘要: 经典背包，记录路径，放得下就行。  阅读全文
posted @ 2009-05-12 19:41 Going 阅读(622) | 评论 (2)  编辑
zju 1503 One Person "The Price is Right"      摘要: 1503 估价游戏，一个决策为背景的 DP，当前剩下 i 次机会和 j 条命，最优的策略可以覆盖 DP[i][j] 范围内的所有情况，那么DP[0][j] = 0, DP[i][0] = i, DP[i][j] = DP[i-1][j-1] + 1 + DP[i-1][j]。
  阅读全文
posted @ 2009-05-11 20:31 Going 阅读(192) | 评论 (0)  编辑
hdu 1978 how many ways      摘要: 这题我觉得DP 比 DFS好  阅读全文
posted @ 2009-05-08 21:35 Going 阅读(213) | 评论 (0)  编辑
zju 2765 Recursively Palindromic Partitions
posted @ 2009-05-08 08:14 Going 阅读(251) | 评论 (0)  编辑
zju 2852 Deck of Cards      摘要: 07年省赛题
用到了四维dp  阅读全文
posted @ 2009-05-06 18:59 Going 阅读(148) | 评论 (0)  编辑
zju 2975 Kinds of Fuwas      摘要: 没看出来有dp的思想，还是同学教的~  阅读全文
posted @ 2009-05-04 14:23 Going 阅读(223) | 评论 (0)  编辑
zju 2972 Hurdles of 110m      摘要: 08年浙江省赛的一个dp题~  阅读全文
posted @ 2009-05-03 10:57 Going 阅读(205) | 评论 (0)  编辑
hdu 1078 FatMouse and Cheese      摘要: 记忆化深搜，注意方向和跳的步数！  阅读全文
posted @ 2009-05-02 18:49 Going 阅读(506) | 评论 (0)  编辑
hdu 1500 Chopsticks      摘要: 参考了下别人的代码，dp真是千变万化啊！
这与搬寝室还是有很大不同的，要倒过来做；
dp[物品组数][物品个数](I为I副筷子，J为总共筷子)
现在转入正题,这个题目要求每一组有3个筷子,前2个的差的平方最小,
首先和前面题目一样先排序对把,显然从大到小排(因为这样完全可以转化成搬寝室 那个一样的思想)
比如取第2队物品,那么第一对已经取完保存在数组里面了,
那么从s[2][3*2+1]计算到s[2][n],
为什么这样就可以呢?
仔细想下,第2组,前面只要有2个可以作为最大的筷子了,一定满足题目意思的了,所以一直计算下去,
状态转移方程和前面一样~
dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1]);
ps:排序从大到小很精妙~  阅读全文
posted @ 2009-04-29 14:39 Going 阅读(179) | 评论 (0)  编辑
hdu 1421 搬寝室      摘要: 由于数据还是比较大的，初始化时一定要足够大，很容易错！
dp[i][j] 从前i个物品中选取j对物品。  阅读全文
posted @ 2009-04-29 13:06 Going 阅读(190) | 评论 (0)  编辑
hdu 2670 Girl Love Value      摘要: dp[i][j] 从前i个人中选j个的最优值。
底层为从前i个选1个。  阅读全文
posted @ 2009-04-28 18:22 Going 阅读(199) | 评论 (0)  编辑
hdu 2059 龟兔赛跑      摘要: 在同学的悉心教导之下总算做对了，虽然还不是很懂~  阅读全文
posted @ 2009-04-27 20:21 Going 阅读(332) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包转化为0-1背包  阅读全文
posted @ 2009-04-25 20:12 Going 阅读(288) | 评论 (0)  编辑
hdu 2602 Bone Collector      摘要: 0-1 背包  阅读全文
posted @ 2009-04-24 14:53 Going 阅读(299) | 评论 (0)  编辑
hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活      摘要: 0-1背包的例子  阅读全文
posted @ 2009-04-24 14:30 Going 阅读(425) | 评论 (0)  编辑
hdu 1159 Common Subsequence 最大公共子序列      摘要: dp[i][j]记录第一个串的前i个字符与第二个串的前j个字符的最大公共子序列的个数。  阅读全文
posted @ 2009-04-24 10:42 Going 阅读(161) | 评论 (0)  编辑
hdu 1087 Super Jumping! Jumping! Jumping!      摘要: 最大递增序列的一点变形！  阅读全文
posted @ 2009-04-23 20:08 Going 阅读(204) | 评论 (0)  编辑
hdu 2512 一卡通大冒险      摘要: 当被分成一堆和n堆的时候都只有一种情况，要在实现初始化。
重要的推导：dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * j)  阅读全文
posted @ 2009-04-23 14:17 Going 阅读(256) | 评论 (0)  编辑
ZOJ 3182 /HUTC 1045 Nine Interlinks      摘要: 找规律哦~~  阅读全文
posted @ 2009-04-23 08:26 Going 阅读(234) | 评论 (0)  编辑
 

 
Powered by:
C++博客
Copyright © Going