HDU 1085 Holding Bin-Laden Captive!(DP)
2024-10-15 23:38:17
题目链接: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.
#include<cstdio> struct node
{
int a,b,c;
}dp[];
int main()
{
int n1,n2,n5;
while(scanf("%d%d%d",&n1,&n2,&n5),n1+n2+n5)
{
dp[].a = ;
dp[].b = ;
dp[].c = ;
int ans = ;
for(int i = ;i <= n1 + *n2+*n5+;++i) //加1是在所有的都能实现的情况下可以直接得到比总数大1的结果
{
if(i >= && dp[i-].a+ <= n1)
dp[i] = dp[i-],dp[i].a += ;
else if(i >= && dp[i-].b+ <= n2)
dp[i] = dp[i-],dp[i].b += ;
else if(i >= && dp[i-].c+ <= n5)
dp[i] = dp[i-],dp[i].c += ;
else
{
ans = i;
break;
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 云与备份之(1):VMware虚机备份和恢复
- HDU 5651 计算回文串个数问题(有重复的全排列、乘法逆元、费马小定理)
- 【原创】angularjs1.3.0源码解析之directive
- OPENSSL 学习整理-介绍
- SQL数据库面试题
- Java基础——运算符
- [Tyvj1001]第K极值 (贪心?模拟)
- python的list和tuple
- Capacity To Ship Packages Within D Days LT1011
- js 中引用类型 的深拷贝 和 浅拷贝的区别
- c++11 noexcept修饰符
- JVM内存管理机制
- redis安装之zmalloc.h:55:2: error: #error ";Newer version of jemalloc required";错误
- Knockout.js Style绑定
- 一个没有成就而即将退赛的OIer的告别书
- window 10下 MySql5.7压缩包安装
- JAVA单态设计模式
- 【考试记录】4.8 Path (网络流 —— 劲题)
- BFC与边距重叠详解
- matlab任务:FCM分类