hdu 2069 普通母函数 +dp

2023-10-23 15:38

文章标签 函数 dp hdu 普通 2069

本文主要是介绍hdu 2069 普通母函数 +dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门：点击打开链接

一开始做题并没有想到Your program should be able to handle up to 100 coins.这句话什么意思，也没有当回事。。但是wa几次，我就感觉只是套模版应该是不对的，但是又找不到，后来我在论坛上看到写着总的硬币个数不能超过100，才知道有条件限制。但是接下来该怎么利用这条件呢？母函数模版只是能得出最后的结果，并不能求出m个硬币凑成的这个n价值的方法数，所以我们利用母函数的求解问题的思路，用二维数组c1[][]来代替c1[],c1[i][j] i其实与模版中的i含义一样(表示凑成i的价值),那么j 代表用了j个硬币凑成i 所以c1[i][j]代表 j个硬币凑成i的方法个数。所以在求的价值为n的时候，我们只要判断硬币个数是否大与100就可以了。这不懂的话可以看一下代码。。（注释的不用看）后面的注释为个别数据。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int f[]={0,1,5,10,25,50};
int c1[300][110],c2[300][110];
int n;
void solve()
{memset(c1,0,sizeof(c1));memcpy(&c2,&c1,sizeof(c1));c1[0][0]=1;for(int i=1;i<=n&&i<=100;++i)c1[i][i]=1;for(int i=2;i<=5;++i){for(int j=0;j<=n;++j){//if(c1[j][0])//{for(int k=0;k+j<=n;k+=f[i]){for(int kk=0;k/f[i]+kk<=100;++kk)//判断条件{if(c1[j][kk]){c2[j+k][kk+k/f[i]]+=c1[j][kk];//if(j+k==115)//  cout<<j<<" "<<kk<<' '<<c1[j][kk]<<endl;}}}}memcpy(&c1,&c2,sizeof(c2));memset(c2,0,sizeof(c2));}int ans=0;for(int i=0;i<=100;++i)ans+=c1[n][i];cout<<ans<<endl;// cout<<c1[n][0]<<endl;
}
int main(int argc, const char * argv[])
{while(cin>>n){solve();}return 0;
}
//n      ans
//0      1
//250   3830//110   380//115   430//100   292//101   291

Coin Change

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18203 Accepted Submission(s): 6268

Problem Description

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.

Input

The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

Sample Input