PKU 1432 Decoding Morse Sequences
http://poj.org/problem?id=1432
モールス信号とそれに含まれうる単語のリストが与えられる。
モールス信号は何通りの文章に解釈可能かを答えろというような問題。
最初にO(n^2)でTLEして、あとに、O(nlogn)ぐらいにまで落とせたけれど、WAになって原因が分からなかったので、データセットとってきてしまいました。
単語リストが同じ信号になっている場合の考慮をし忘れていました。
ll dp[10100]; string in; string to[128]; string mo[]={".-","-...","-.-.","-..", ".","..-.","--.","....", "..",".---","-.-",".-..", "--","-.","---",".--.", "--.-",".-.","...","-", "..-","...-",".--","-..-", "-.--","--..", }; main(){ for(int i='A';i<='Z';i++){ to[i]=mo[i-'A']; } int t; cin>>t; while(t--){ map<string,int> app; cin>>in; memset(dp,0,sizeof(dp)); dp[0]=1; int n; cin>>n; int msz=0; rep(i,n){ string temp; string dict=""; cin>>temp; rep(j,SZ(temp))dict+=to[temp[j]]; app[dict]++; msz=max(msz,SZ(dict)); } rep(i,SZ(in)){ string tt; rep(j,msz){ if(i+j>=SZ(in))break; tt+=in[i+j]; if(app.count(tt))dp[i+j+1]+=dp[i]*app[tt]; } } cout<<dp[SZ(in)]<<endl; } }