PKU 1790 Base Numbers
http://poj.org/problem?id=1790
与えられた数字列を数字と基数の組み合わせと見た時、何通りの表記として解釈できるかを答えろというような問題。
0の扱いに注意してやる必要がある以外はだいたいDP。
2回WAをもらいました。
サンプルだけだと不親切なので、問題分の数字列についても試すべきでした。
string in; string base; ll memo[100]; bool vis[100]; bool ok(int s,int e){ if((e-s>1 && in[s]=='0') || SZ(base)<e-s)return false; if(s==0 && e==1 && in[0]=='0' && e+SZ(base)!=SZ(in))return false; if(SZ(base)>e-s)return true; for(int i=0;i<SZ(base);++i){ if(base[i]<in[s+i])return false; if(base[i]>in[s+i])return true; } return false; } ll rec(int p){ if(p==0)return 1; if(vis[p])return memo[p]; vis[p]=true; ll& ret=memo[p]=0; rep(i,p) if(ok(i,p))ret+=rec(i); return ret; } void solve(){ ll ans=0; for(int i=1;i<SZ(in);++i){ if(in[i]=='0')continue; memset(vis,0,sizeof(vis)); base=in.substr(i); ans+=rec(i); } cout<<"The code "<<in<<' '; if(ans)cout<<"can represent "<<ans<<" numbers."<<endl; else cout<<"is invalid."<<endl; } main(){ while(cin>>in,in!="#") solve(); }