PKU 3181 Dollar Dayz
http://poj.org/problem?id=3181
nドルのものを1〜Kドルまでの貨幣で支払うとき、何通りの支払い方があるかを答えろというような問題。
多倍長+DP。
遅い多倍長でTLEもらいました。
char* add(char* a,char* b,char* out){ int as=strlen(a),bs=strlen(b); int c=0; int sz=0; rep(i,max(as,bs)){ int t=c; if(i<as)t+=a[i]-'0'; if(i<bs)t+=b[i]-'0'; c=t/10; t%=10; out[sz++]=t+'0'; } if(c)out[sz++]=c+'0'; out[sz]=0; return out; } char dp[1100][110][40]; bool vis[1100][110]; char zero[]="0"; char one[]="1"; char* rec(int n,int k){ if(n<0 || k<1)return zero; if(n==0)return one; if(vis[n][k])return dp[n][k]; vis[n][k]=true; return add(rec(n,k-1),rec(n-k,k),dp[n][k]); } main(){ int n,k; cin>>n>>k; string ans(rec(n,k)); reverse(ALL(ans)); cout<<ans<<endl; }