首页 > 代码库 > HDU 1085 Holding Bin-Laden Captive!(DP)
HDU 1085 Holding Bin-Laden Captive!(DP)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1085
解题报告：有1,2,5三种面值的硬币，这三种硬币的数量分别是num_1,num_2,num_5，问你不能凑的钱的最小值是多少。
DP，开一个这样的数组dp[i][3]，然后dp[i][0]表示凑成 i 元钱需要dp[i][0]张1块的，需要dp[i][1]张两块的，dp[i][2]张5块的，然后依次往后递推，得到 i 的途径一共有三种，第一种是i-1加一张一块的，第二种是i-2加上1张两块的，第四种是i-5加上一张5块的，然后每次判断一下有没有超过张数就行了，如果发现这三种途径都不能凑成i，那么说明最小的不能凑的值就是i.
1 #include<cstdio> 2 3 struct node 4 { 5 int a,b,c; 6 }dp[8005]; 7 int main() 8 { 9 int n1,n2,n5;10 while(scanf("%d%d%d",&n1,&n2,&n5),n1+n2+n5)11 {12 dp[0].a = 0;13 dp[0].b = 0;14 dp[0].c = 0;15 int ans = 0;16 for(int i = 1;i <= n1 + 2*n2+5*n5+1;++i) //加1是在所有的都能实现的情况下可以直接得到比总数大1的结果 17 {18 if(i >= 1 && dp[i-1].a+1 <= n1)19 dp[i] = dp[i-1],dp[i].a += 1;20 else if(i >= 2 && dp[i-2].b+1 <= n2)21 dp[i] = dp[i-2],dp[i].b += 1;22 else if(i >=5 && dp[i-5].c+1 <= n5)23 dp[i] = dp[i-5],dp[i].c += 1;24 else25 {26 ans = i;27 break;28 }29 }30 printf("%d\n",ans);31 }32 return 0;33 }34 35
HDU 1085 Holding Bin-Laden Captive!(DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。