首页 > 代码库 > HDU2069 Coin Change (DP)
HDU2069 Coin Change (DP)
题目意思:
http://acm.hdu.edu.cn/showproblem.php?pid=2069
给你五种硬币:1,5,10,25,50,现在给出一个n,求出用用这些组成价值n的种类数,例如n=11;
1、11个1
2、1个10,1个1
3、1个5,6个1
4、2个5,1个1
特别注意:使用硬币数不能超过100,只要注意了这个就可以了。
AC代码:
/** *@xiaoran *dp[i],最多100枚硬币 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; const int a[5]={1,5,10,25,50}; LL dp[255][101];//dp[j][k]:用k个硬币组成j值的个数 int main() { int n; while(cin>>n){ //cout<<res[n]<<endl; memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=0;i<5;i++){ for(int k=1;k<=100;k++){//k个硬币 for(int j=a[i];j<=n;j++){ dp[j][k]+=dp[j-a[i]][k-1]; } } } int res=0; for(int i=0;i<=100;i++){ res+=dp[n][i]; } cout<<res<<endl; } return 0; }
HDU2069 Coin Change (DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。