Rotate and Rewrite (AOJ1191)
クッッッッッッソ良問だと思う
問題:文字列に対し,rotate(abcd->dabc)とrewrite(与えられたルール(文字列と文字のペア)に対し,今の文字列のsubstringとしてその文字列が現れたらそれをその文字に置き換える)が好きな順で何回も行える.文字列が二つ(A,B)与えられるのでそれぞれ独立に操作して同じ文字列にせよ.その時の長さmax(無理なら-1)を出力せよ.
A,Bの長さ<=25,文字種類30,ルールの数60,ルールに現れる方の文字列の長さ<10
頭5,実装1,ライブラリ0,気合2
dpが二つあることに気づけばおしまいだけどこれ難しいと思うんですよね・・・
1つ目は,substring A[i..j]を文字xに出来るか? で,これを計算するには,A[i..j]をルールxのk文字目までに出来るか?と共にdpしてけばよい.
2つ目は,元の文字列AとBに対して,cycleの始まる点を全探索し,その後,Aをx文字目まで,Bをy文字目まで見た時に(そいつらを変換した結果として)何文字一致させられるか を求めれば良い.
両方とも簡単なDPだけど,二つ合わせると真ん中がすっぽり抜けてるせいですごい気づきにくいんですよね・・・
まあ発想としては,文字列を持つのは不可能→各文字に対して考えれば良いのでは だからまあ典型ではある.
部分問題を解くことの有用性がわかる良問だった.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; int N,M,R,a[50],b[50],n[60],f[60][10]; int t[60]; bool canA[50][50][30],canB[50][50][30]; //[i,j) でkを作れるか? bool tmp[50][50][60][10]; //[i,j)でrule k のl文字目まで作れるか? void calccan(int* a,int N,bool can[50][50][30]){ rep(i,50) rep(j,50) rep(k,30) can[i][j][k]=0; rep(i,50) rep(j,50) rep(k,60) rep(l,10) tmp[i][j][k][l]=(i==j&&l==0); rep(i,N*2-1) can[i][i+1][a[i]]=1; rep1(len,N){ for(int l=0;l+len<=2*N-1;l++){ int r=l+len; rep(i,R) rep1(j,n[i]){ for(int x=l;x<r;x++){ if(tmp[l][x][i][j-1]&&can[x][r][f[i][j-1]]) tmp[l][r][i][j]=1; } } rep(i,R) if(tmp[l][r][i][n[i]]) can[l][r][t[i]]=1; rep(i,R) if(can[l][r][f[i][0]]) tmp[l][r][i][1]=1; } } } int main(){ while(true){ cin>>N>>M>>R; if(N==0) break; rep(i,N) cin>>a[i],a[i]--; rep(i,N) a[i+N]=a[i]; rep(i,M) cin>>b[i],b[i]--; rep(i,M) b[i+M]=b[i]; rep(i,R){ cin>>n[i]; rep(j,n[i]) cin>>f[i][j],f[i][j]--; cin>>t[i],t[i]--; } calccan(a,N,canA); calccan(b,M,canB); int ans=-1; rep(x,N) rep(y,M){ //start int dp[26][26]={}; rep(i,N+1) rep(j,M+1) dp[i][j]=-1; dp[0][0]=0; rep(i,N+1) rep(j,M+1){ if(dp[i][j]<0) continue; rep(k,30){ rep1(c,N-i) rep1(d,M-j){ if(canA[x+i][x+i+c][k]&&canB[y+j][y+j+d][k]) chmax(dp[i+c][j+d],dp[i][j]+1); } } } chmax(ans,dp[N][M]); } cout<<ans<<endl; } }