http://poj.org/problem?id=3181
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 7997 | Accepted: 2992 |
Description
1 @ US$3 + 1 @ US$2Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1
Input
Output
Sample Input
5 3
Sample Output
5
Source
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct Bign 6 { 7 int a[105]; 8 void out() 9 { 10 for(int i=a[0];i>=1;--i) 11 printf("%d",a[i]);puts(""); 12 } 13 }f[1015]; 14 void add(Bign &e,Bign &x){ 15 int limit=max(e.a[0],x.a[0]); 16 e.a[0]=limit; 17 for(int i=1;i<=limit;++i) 18 e.a[i]+=x.a[i]; 19 for(int i=1;i<=e.a[0];++i) 20 { 21 if(e.a[i]>9){ 22 e.a[i+1]++; 23 e.a[i]%=10; 24 } 25 if(e.a[e.a[0]+1]) e.a[0]++; 26 } 27 } 28 int main() 29 { 30 int N,K,i,j; 31 while(cin>>N>>K){ 32 for(i=0;i<=N;++i){ 33 memset(f[i].a,0,sizeof(f[i].a)); 34 f[i].a[0]=1; 35 } 36 f[0].a[1]=1; 37 for(i=1;i<=K;++i) 38 for(j=i;j<=N;++j){ 39 add(f[j],f[j-i]); 40 } 41 f[N].out(); 42 } 43 return 0; 44 }
原文：http://www.cnblogs.com/zzqc/p/7777664.html