DP

hdu 2670 Girl Love Value      摘要: dp
按损耗值由大到小排序  阅读全文
posted @ 2009-05-17 21:28 Going 阅读(276) | 评论 (0)  编辑
hdu 2372 El Dorado
posted @ 2009-05-14 20:24 Going 阅读(272) | 评论 (1)  编辑
zju 1520 Duty Free Shop      摘要: 经典背包,记录路径,放得下就行。  阅读全文
posted @ 2009-05-12 19:41 Going 阅读(571) | 评论 (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 阅读(184) | 评论 (0)  编辑
hdu 1978 how many ways      摘要: 这题我觉得DP 比 DFS好  阅读全文
posted @ 2009-05-08 21:35 Going 阅读(200) | 评论 (0)  编辑
zju 2852 Deck of Cards      摘要: 07年省赛题
用到了四维dp  阅读全文
posted @ 2009-05-06 18:59 Going 阅读(140) | 评论 (0)  编辑
zju 2975 Kinds of Fuwas      摘要: 没看出来有dp的思想,还是同学教的~  阅读全文
posted @ 2009-05-04 14:23 Going 阅读(209) | 评论 (0)  编辑
zju 2972 Hurdles of 110m      摘要: 08年浙江省赛的一个dp题~  阅读全文
posted @ 2009-05-03 10:57 Going 阅读(198) | 评论 (0)  编辑
hdu 1078 FatMouse and Cheese      摘要: 记忆化深搜,注意方向和跳的步数!  阅读全文
posted @ 2009-05-02 18:49 Going 阅读(496) | 评论 (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 阅读(171) | 评论 (0)  编辑
hdu 1421 搬寝室      摘要: 由于数据还是比较大的,初始化时一定要足够大,很容易错!
dp[i][j] 从前i个物品中选取j对物品。  阅读全文
posted @ 2009-04-29 13:06 Going 阅读(181) | 评论 (0)  编辑
hdu 2670 Girl Love Value      摘要: dp[i][j] 从前i个人中选j个的最优值。
底层为从前i个选1个。  阅读全文
posted @ 2009-04-28 18:22 Going 阅读(144) | 评论 (0)  编辑
hdu 2059 龟兔赛跑      摘要: 在同学的悉心教导之下总算做对了,虽然还不是很懂~  阅读全文
posted @ 2009-04-27 20:21 Going 阅读(281) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包转化为0-1背包  阅读全文
posted @ 2009-04-25 20:12 Going 阅读(239) | 评论 (0)  编辑
hdu 2602 Bone Collector      摘要: 0-1 背包  阅读全文
posted @ 2009-04-24 14:53 Going 阅读(290) | 评论 (0)  编辑
hdu 1159 Common Subsequence 最大公共子序列      摘要: dp[i][j]记录第一个串的前i个字符与第二个串的前j个字符的最大公共子序列的个数。  阅读全文
posted @ 2009-04-24 10:42 Going 阅读(150) | 评论 (0)  编辑
hdu 1087 Super Jumping! Jumping! Jumping!      摘要: 最大递增序列的一点变形!  阅读全文
posted @ 2009-04-23 20:08 Going 阅读(198) | 评论 (0)  编辑
hdu 2512 一卡通大冒险      摘要: 当被分成一堆和n堆的时候都只有一种情况,要在实现初始化。
重要的推导:dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * j)  阅读全文
posted @ 2009-04-23 14:17 Going 阅读(247) | 评论 (0)  编辑
ZOJ 3182 /HUTC 1045 Nine Interlinks      摘要: 找规律哦~~  阅读全文
posted @ 2009-04-23 08:26 Going 阅读(223) | 评论 (0)  编辑