AOJ 1191: Rotate and Rewrite

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);
	}
}