dp[i][j][k]: [i,j]を文字kにできるか、でDP。
言われてみれば確かになあという感じだし、問題の自由度の低さ的にもこれしかない、という状態の持ち方だから、気がつけるとも思うんだけど絶妙だなあ。
あと、結構このオーダーが重いのとこの後のおまけDPもオーダー重めなので、30個まとめてビットで管理するとかなり速度がかわります。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int dp[2][32][32][32]; vector<int>r[62]; int to[62]; int p[30]; int q[30]; int n,m,s; int calc(int a,int b,int c,int d){ //printf("%d %d %d %d\n",a,b,c,d); if(~dp[a][b][c][d])return dp[a][b][c][d]; if(b==c){ if(a==0){ if(d==p[b])return dp[a][b][c][d]=1; else return dp[a][b][c][d]=0; }else{ if(d==q[b])return dp[a][b][c][d]=1; else return dp[a][b][c][d]=0; } } int len=c-b+1; if(len<=0){ if(!a)len+=n;else len+=m; } for(int v=0;v<s;v++){ if(to[v]!=d)continue; int dp3[32][32]; for(int i=0;i<32;i++)for(int j=0;j<32;j++)dp3[i][j]=0; dp3[0][0]=1; // if(a==1&&b==1&&c==0&&d==0&&v==2)printf("%d %d\n",(int)r[v].size(),len); for(int i=0;i<r[v].size();i++)for(int j=0;j<len;j++){ if(!dp3[i][j])continue; // if(a==1&&b==1&&c==0&&d==0&&v==2)printf("%d %d\n",i,j); for(int k=j;k<len;k++){ if(j==0&&k==len-1)continue; int L=b+j; if(!a)L%=n; else L%=m; int R=b+k; if(!a)R%=n; else R%=m; if(calc(a,L,R,r[v][i]))dp3[i+1][k+1]=1; } } if(dp3[r[v].size()][len])return dp[a][b][c][d]=1; } return dp[a][b][c][d]=0; } int dpv[2][32][32]; int dp2[32][32]; int main(){ int a,b,c; while(scanf("%d%d%d",&a,&b,&c),a){ n=a;m=b;s=c; for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<a;i++)p[i]--; for(int i=0;i<b;i++)scanf("%d",q+i); for(int i=0;i<b;i++)q[i]--; for(int i=0;i<62;i++)r[i].clear(); for(int i=0;i<c;i++){ int d;scanf("%d",&d); for(int j=0;j<d;j++){ int e;scanf("%d",&e); e--; r[i].push_back(e); } scanf("%d",to+i); to[i]--; } for(int i=0;i<2;i++)for(int j=0;j<32;j++) for(int k=0;k<32;k++)for(int l=0;l<32;l++) dp[i][j][k][l]=-1; for(int i=0;i<a;i++)for(int j=0;j<a;j++)for(int k=0;k<30;k++){ // printf("%d %d %d %d\n",0,i,j,k); calc(0,i,j,k); // if(dp[0][i][j][k])printf("%d %d %d %d\n",0,i,j,k); } for(int i=0;i<b;i++)for(int j=0;j<b;j++)for(int k=0;k<30;k++){ // printf("%d %d %d %d\n",1,i,j,k); calc(1,i,j,k); // if(dp[1][i][j][k])printf("%d %d %d %d\n",1,i,j,k); } for(int i=0;i<2;i++)for(int j=0;j<32;j++)for(int k=0;k<32;k++){ dpv[i][j][k]=0; } for(int i=0;i<a;i++)for(int j=0;j<a;j++)for(int k=0;k<30;k++)if(dp[0][i][j][k]) dpv[0][i][j]+=(1<<k); for(int i=0;i<b;i++)for(int j=0;j<b;j++)for(int k=0;k<30;k++)if(dp[1][i][j][k]) dpv[1][i][j]+=(1<<k); int ret=-1; for(int i=0;i<n;i++){ for(int v=0;v<m;v++){ for(int j=0;j<32;j++)for(int k=0;k<32;k++)dp2[j][k]=-999999999; dp2[0][0]=0; for(int j=0;j<n;j++){ for(int k=0;k<m;k++){ for(int f=j;f<n;f++)for(int g=k;g<m;g++){ if(dpv[0][(i+j)%n][(i+f)%n]&dpv[1][(v+k)%m][(v+g)%m])dp2[f+1][g+1]=max(dp2[f+1][g+1],dp2[j][k]+1); } } } ret=max(ret,dp2[n][m]); } } printf("%d\n",ret); } }
