题意： 有50 25 10 5 1 的硬币 一共最多有100枚 输入n输出有多少种表示方法
Sample Input
11
26
Sample Output
4
13
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <string> 6 # include <cmath> 7 # include <queue> 8 # include <list> 9 # define LL long long 10 using namespace std ; 11 12 int c1[300][110],c2[300][110]; 13 int ans[300] ; 14 int w[6]={0,1,5,10,25,50}; 15 16 void Init(){ 17 memset(c1,0,sizeof(c1)); 18 memset(c2,0,sizeof(c2)); 19 c1[0][0]=1; 20 for(int i=1;i<=5;i++) 21 { 22 for(int j=0;j<=250;j++) 23 for(int k=0;j+k*w[i]<=250;k++) 24 for(int p=0;k+p<=100;p++) 25 c2[j+k*w[i]][p+k]+=c1[j][p]; 26 27 for(int j=0;j<=250;j++) 28 for(int p=0;p<=100;p++) 29 { 30 c1[j][p]=c2[j][p]; 31 c2[j][p]=0; 32 } 33 } 34 for(int i=1;i<=250;i++) 35 for(int j=0;j<=100;j++) 36 ans[i]+=c1[i][j]; //c1[11][3]表示这个方案 是用3枚硬币组成11的 37 ans[0]=1; 38 } 39 40 int main() 41 { 42 43 int n; 44 Init(); 45 while(~scanf("%d",&n)) 46 { 47 printf("%d ",ans[n]); 48 } 49 return 0; 50 }