DP

hdu 2670 Girl Love Value      摘要: dp
按损耗值由大到小排序  阅读全文
posted @ 2009-05-17 21:28 Going 阅读(195) | 评论 (0)  编辑
hdu 2372 El Dorado
posted @ 2009-05-14 20:24 Going 阅读(176) | 评论 (1)  编辑
zju 1520 Duty Free Shop      摘要: 经典背包,记录路径,放得下就行。  阅读全文
posted @ 2009-05-12 19:41 Going 阅读(403) | 评论 (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 阅读(136) | 评论 (0)  编辑
hdu 1978 how many ways      摘要: 这题我觉得DP 比 DFS好  阅读全文
posted @ 2009-05-08 21:35 Going 阅读(161) | 评论 (0)  编辑
zju 2852 Deck of Cards      摘要: 07年省赛题
用到了四维dp  阅读全文
posted @ 2009-05-06 18:59 Going 阅读(91) | 评论 (0)  编辑
zju 2975 Kinds of Fuwas      摘要: 没看出来有dp的思想,还是同学教的~  阅读全文
posted @ 2009-05-04 14:23 Going 阅读(147) | 评论 (0)  编辑
zju 2972 Hurdles of 110m      摘要: 08年浙江省赛的一个dp题~  阅读全文
posted @ 2009-05-03 10:57 Going 阅读(134) | 评论 (0)  编辑
hdu 1078 FatMouse and Cheese      摘要: 记忆化深搜,注意方向和跳的步数!  阅读全文
posted @ 2009-05-02 18:49 Going 阅读(428) | 评论 (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 阅读(106) | 评论 (0)  编辑
hdu 1421 搬寝室      摘要: 由于数据还是比较大的,初始化时一定要足够大,很容易错!
dp[i][j] 从前i个物品中选取j对物品。  阅读全文
posted @ 2009-04-29 13:06 Going 阅读(121) | 评论 (0)  编辑
hdu 2670 Girl Love Value      摘要: dp[i][j] 从前i个人中选j个的最优值。
底层为从前i个选1个。  阅读全文
posted @ 2009-04-28 18:22 Going 阅读(49) | 评论 (0)  编辑
hdu 2059 龟兔赛跑      摘要: 在同学的悉心教导之下总算做对了,虽然还不是很懂~  阅读全文
posted @ 2009-04-27 20:21 Going 阅读(175) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包转化为0-1背包  阅读全文
posted @ 2009-04-25 20:12 Going 阅读(121) | 评论 (0)  编辑

Full DP Archive