3458 Colour Sequence

問題概要

カードの列がある。それぞれのカードの表と裏にはアルファベット一文字で表わされる色が塗られている。

今、色の列Sが与えられる。
カードの列のカードを、好きなようにひっくり返して列を作り、その列の（連続するとは限らない）部分列としてSを含むことができるかを判定せよ。

Sの長さおよびカードの列の枚数は100以下とする。

解法

編集距離みたいなDP.
列のi番目までとSのj番目までの一致をdp[i][j]としたときに、
dp[i][j-1],dp[i-1][j],dp[i-1][j-1]を見ることで漸化式が作れる。

ソースコード

int n,m,T,dp[101][101];
char s[101],p[101],q[101];
bool ok(char a,char b,char c){
	if(b=='*'||c=='*')return 1;
	return a==b||a==c;
}
int main(){
	scanf("%d",&T);
	rep(U,T){
		scanf("%s%s%s",s,p,q);
		n=strlen(s); m=strlen(p);
		rep(i,n+1)rep(j,m+1)dp[i][j]=0;
		rep(i,n)rep(j,m){
			dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
			if(ok(s[i],p[j],q[j]))dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
		}
		puts(dp[n][m]==n?"win":"lose");
	}
	return 0;
}