2012年9月15日 HDU 1171 Big Event in HDU 动态规划多重背包 摘要: 题意: 给定你每种设备的价值和数量要你将这些设备平分( 就算不是刚好平分也要尽量接近).坑爹: 一开始看到这题是一点思路都没有以为一定要刚好平分数组要开到 50 * 50 * 100 .解法: 只要将所
2012年9月15日 HDU 1171 Big Event in HDU 动态规划多重背包 摘要: 题意: 给定你每种设备的价值和数量要你将这些设备平分( 就算不是刚好平分也要尽量接近).坑爹: 一开始看到这题是一点思路都没有以为一定要刚好平分数组要开到 50 * 50 * 100 .解法: 只要将所有设备的价值加起来(sum)然后利用多重背包但 背包 的容量不是sum而是sum/2这样就可以找出当 背包 的容量为总价值一半的时候的最优情况然后另外一边分到的设备就是 sumDP[sum/2] .View Co阅读全文posted @ 19:22 pc阅读(13) 评论(0) 编辑 HDU 1114 Piggy-Bank 动态规划完全背包 摘要: 题意: 有T组测试数据，
.坑爹: 因为他是要,后面的E和F分别表示存钱罐空的时候的重量和满了的时候的重量然后有个m ,代表下面有 m 种钱币每种钱币分别有他的面值和重量要你求出当存钱罐满的时候存钱罐中至少有多少钱.坑爹: 因为他是要求出最少有多少钱所以要 DP[ j ] = max ( DP [j ]DP[ jcost ]weight )还有一点要注意的是DP数组的初始化要初始化为最大值因为它每次都要求最小的一种情况DP[0] = 0是递推的一个开始.解法..阅读全文posted @ 17:45 pc阅读(12) 评论(0) 编辑 HDU 1237 简单计算器 栈 摘要: 题意: 给你一个只有* / 的计算表达式要你求出结果.坑爹: 一开始我只是以为只要在输入的时候遇到*或者/就弹出来进行计算,然后在到最后计算和的时候直接弹出一个一个计算,最后才发现原来在最后弹出来计算的时候要全部反过来,不能直接弹出就计算然后压入.解法: 遇到 * 或者 / 就弹出两个进行计算, 然后压入结果到最后的时候把栈里的数字反过来,也就是用一个数组从0n开始存每一个出栈的数字符号栈也是相同的操作然后就可以进行正常的按顺序这样做和阅读全文posted @ 17:37 pc阅读(22) 评论(0) 编辑