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 阅读(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 阅读(149) | 评论 (0)  编辑
hdu 1074 Doing Homework      摘要: 这题本来是在dp专题里的，或许这里是记忆化搜索吧！不是很明白的！  阅读全文
posted @ 2009-04-28 17:38 Going 阅读(317) | 评论 (0)  编辑
hdu 2059 龟兔赛跑      摘要: 在同学的悉心教导之下总算做对了，虽然还不是很懂~  阅读全文
posted @ 2009-04-27 20:21 Going 阅读(286) | 评论 (0)  编辑
hdu 1203 I NEED A OFFER!      摘要: 原以为是用DP做的，但就是不会写，后来才知道用贪心就可以了！  阅读全文
posted @ 2009-04-26 09:27 Going 阅读(504) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包转化为0-1背包  阅读全文
posted @ 2009-04-25 20:12 Going 阅读(244) | 评论 (0)  编辑
hdu 2602 Bone Collector      摘要: 0-1 背包  阅读全文
posted @ 2009-04-24 14:53 Going 阅读(290) | 评论 (0)  编辑
hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活      摘要: 0-1背包的例子  阅读全文
posted @ 2009-04-24 14:30 Going 阅读(413) | 评论 (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)  编辑
hdu 1059 Windows Message Queue      摘要: 很好的使用优先队列的例子！  阅读全文
posted @ 2009-04-23 13:08 Going 阅读(241) | 评论 (0)  编辑
hdu 1195 Open the Lock      摘要: 广搜，方向为加一，减一，相邻交换，注意10和0的处理！  阅读全文
posted @ 2009-04-23 13:05 Going 阅读(103) | 评论 (0)  编辑
hdu 1195 Open the Lock      摘要: 广搜，方向为加一，减一，相邻交换，注意10和0的处理！  阅读全文
posted @ 2009-04-23 13:05 Going 阅读(403) | 评论 (2)  编辑
hdu 1241 Oil Deposits      摘要: 深搜，广搜都可以！  阅读全文
posted @ 2009-04-23 13:01 Going 阅读(226) | 评论 (0)  编辑
hdu 1016 Prime Ring Problem      摘要: 很基本的深搜题，素数环，但是不理解深搜的含义还是不能做的！还好有人教，O(∩_∩)O~  阅读全文
posted @ 2009-04-23 12:55 Going 阅读(166) | 评论 (0)  编辑
ZOJ 3182 /HUTC 1045 Nine Interlinks      摘要: 找规律哦~~  阅读全文
posted @ 2009-04-23 08:26 Going 阅读(224) | 评论 (0)  编辑
hutc 1040 Knapsack Problem 贪心      摘要: 很基础的背包问题，用贪心方法做的！  阅读全文
posted @ 2009-04-22 13:59 Going 阅读(109) | 评论 (0)  编辑
慢慢喜欢ACM
posted @ 2009-04-16 21:06 Going 阅读(280) | 评论 (3)  编辑
 

 
Powered by:
C++博客
Copyright © Going