PKU 1732 Phone numbers
http://poj.org/problem?id=1732
数字から文字への変換表をもとに、ある数字列を与えられた単語リストに出現する単語の列に置き換えて、単語数が最も少ないものを出力しろというような問題。
似たような問題をPKUで解いたような気がします。
動的計画法。
TLEしましたが、ios::sync_with_stdio(0)を加えるだけで通ったので、楽出来たように感じました。
ローカルで実行したとき、サンプルに対して何回かセグフォしたのが謎です。
string ctoid[]={"oqz","ij","absc","def","gh","kl","mn","prs","tuv","wxy"}; int ctoi[200]; string ba[200]; int dp[200]; main(){ ios::sync_with_stdio(0); rep(i,10)FOR(cc,ctoid[i])ctoi[*cc]=i+'0'; memset(dp,-1,sizeof(dp)); string in; cin>>in; int n; cin>>n; map<string,string> ntow; rep(i,n){ string wo; cin>>wo; string nu(SZ(wo),' '); rep(j,SZ(wo))nu[j]=ctoi[wo[j]]; //cout<<wo<<endl; ntow[nu]=wo; } //return 0; dp[0]=0; rep(i,SZ(in)){ if(dp[i]==-1)continue; for(int j=1;j<=min(51,SZ(in)-i);++j){ if((dp[i+j]==-1 || dp[i+j]>dp[i]+1) && ntow.count(in.substr(i,j))){ dp[i+j]=dp[i]+1; ba[i+j]=ntow[in.substr(i,j)]; } } } //return 0; if(dp[SZ(in)]==-1)cout<<"No solution."<<endl; else{ int idx=SZ(in); vector<string> ans; while(idx>0){ ans.pb(ba[idx]); idx-=SZ(ba[idx]); //cout<<idx<<endl; } reverse(ALL(ans)); FOR(it,ans)cout<<*it<<' '; cout<<endl; } }