04 2009 档案

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 阅读(130) | 评论 (0)  编辑
hdu 1421 搬寝室      摘要: 由于数据还是比较大的,初始化时一定要足够大,很容易错!
dp[i][j] 从前i个物品中选取j对物品。  阅读全文
posted @ 2009-04-29 13:06 Going 阅读(125) | 评论 (0)  编辑
hdu 2670 Girl Love Value      摘要: dp[i][j] 从前i个人中选j个的最优值。
底层为从前i个选1个。  阅读全文
posted @ 2009-04-28 18:22 Going 阅读(57) | 评论 (0)  编辑
hdu 1074 Doing Homework      摘要: 这题本来是在dp专题里的,或许这里是记忆化搜索吧!不是很明白的!  阅读全文
posted @ 2009-04-28 17:38 Going 阅读(256) | 评论 (0)  编辑
hdu 2059 龟兔赛跑      摘要: 在同学的悉心教导之下总算做对了,虽然还不是很懂~  阅读全文
posted @ 2009-04-27 20:21 Going 阅读(184) | 评论 (0)  编辑
hdu 1203 I NEED A OFFER!      摘要: 原以为是用DP做的,但就是不会写,后来才知道用贪心就可以了!  阅读全文
posted @ 2009-04-26 09:27 Going 阅读(391) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包转化为0-1背包  阅读全文
posted @ 2009-04-25 20:12 Going 阅读(129) | 评论 (0)  编辑
hdu 2602 Bone Collector      摘要: 0-1 背包  阅读全文
posted @ 2009-04-24 14:53 Going 阅读(252) | 评论 (0)  编辑
hdu 1159 Common Subsequence 最大公共子序列      摘要: dp[i][j]记录第一个串的前i个字符与第二个串的前j个字符的最大公共子序列的个数。  阅读全文
posted @ 2009-04-24 10:42 Going 阅读(117) | 评论 (0)  编辑
hdu 1087 Super Jumping! Jumping! Jumping!      摘要: 最大递增序列的一点变形!  阅读全文
posted @ 2009-04-23 20:08 Going 阅读(151) | 评论 (0)  编辑
hdu 2512 一卡通大冒险      摘要: 当被分成一堆和n堆的时候都只有一种情况,要在实现初始化。
重要的推导:dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * j)  阅读全文
posted @ 2009-04-23 14:17 Going 阅读(201) | 评论 (0)  编辑
hdu 1059 Windows Message Queue      摘要: 很好的使用优先队列的例子!  阅读全文
posted @ 2009-04-23 13:08 Going 阅读(185) | 评论 (0)  编辑
hdu 1195 Open the Lock      摘要: 广搜,方向为加一,减一,相邻交换,注意10和0的处理!  阅读全文
posted @ 2009-04-23 13:05 Going 阅读(49) | 评论 (0)  编辑
hdu 1195 Open the Lock      摘要: 广搜,方向为加一,减一,相邻交换,注意10和0的处理!  阅读全文
posted @ 2009-04-23 13:05 Going 阅读(320) | 评论 (2)  编辑
hdu 1241 Oil Deposits      摘要: 深搜,广搜都可以!  阅读全文
posted @ 2009-04-23 13:01 Going 阅读(161) | 评论 (0)  编辑
hdu 1016 Prime Ring Problem      摘要: 很基本的深搜题,素数环,但是不理解深搜的含义还是不能做的!还好有人教,O(∩_∩)O~  阅读全文
posted @ 2009-04-23 12:55 Going 阅读(111) | 评论 (0)  编辑
ZOJ 3182 /HUTC 1045 Nine Interlinks      摘要: 找规律哦~~  阅读全文
posted @ 2009-04-23 08:26 Going 阅读(165) | 评论 (0)  编辑
hutc 1040 Knapsack Problem 贪心      摘要: 很基础的背包问题,用贪心方法做的!  阅读全文
posted @ 2009-04-22 13:59 Going 阅读(55) | 评论 (0)  编辑
慢慢喜欢ACM
posted @ 2009-04-16 21:06 Going 阅读(135) | 评论 (3)  编辑