TopCoder SRM 342 Div1 Medium ReverseResources
問題
文字列strおよび、要素数nの文字列の配列resources[]が与えられる。
文字列strは、resourcesから次のようにして作った文字列である。
- resourcesの要素どれか一つresources[i]から出発する
- 文字列中の"%s"を、resourcesの別の要素に置換する
- 上の操作を繰り返す
このとき、resourcesからstrを作る作り方は何通りあるか、mod 10^9+7で求めよ。
ただし、resourcesに重複する要素が含まれていても、それらは別々のものとして数えるものとする。
制約条件
strの長さ≦30
resourcesの要素≦50
resoures[i]の長さ≦50
resources[i]は%sだけであることはない
方針
動的計画法(メモ化再帰)による。
rec(i,j,id,pos)を、
元の文字列i文字目からj文字目までを作っていて、
現在resources[id]のpos番目の文字までを作っている状態の場合の数とする。
ただし、idがnのときは、次にどのresources[i]の要素も使えるとする。
これでrec(0,元の文字列の長さ,n,0)を求めてやればよい。
再帰関数の中では、
idがnより小さい場合は、strのl番目の文字と、resources[id]のpos番目の文字が一致しているかを見る。
idがnだったら、resourcesの全てを使ってみて、それぞれの場合の数を合計する。
ソースコード
void replace(string &a,string b,string c){ for(int p=0;(p=a.find(b,p))!=a.npos;p++) a=a.substr(0,p)+c+a.substr(p+b.size()); } const int mod=1000000007; string s; vs v; int n,m,len[51]; int dp[31][31][51][51]; int rec(int l,int r,int id,int pos){ int &res=dp[l][r][id][pos]; if(res>=0)return res; res=0; if(l>r)return 0; if(l==r)return res=id!=n&&pos==len[id]; if(id==n){ rep(i,n)(res+=rec(l,r,i,0))%=mod; return res; } if(pos==len[id])return 0; if(v[id][pos]=='@'){ for(int i=l+1;i<=r;i++){ res+=(ll)rec(l,i,n,0)*rec(i,r,id,pos+1)%mod; res%=mod; } return res; } if(s[l]!=v[id][pos])return 0; return res=rec(l+1,r,id,pos+1); } class ReverseResources { public: int findDecompositions(string str, vector <string> resources) { s=str; v=resources; n=v.size(); m=s.size(); rep(i,n){ replace(v[i],"%s","@"); len[i]=v[i].size(); } memset(dp,-1,sizeof(dp)); return rec(0,m,n,0); } };