POJ2192Zipper

2017/12/05

ただのDPのはずかstrlen()多用しすぎててTLEにになっていた。
気をつけよう。

#include <cstdio>
#include <string.h>
#include <iostream>

using namespace std;
char a[202],b[202],c[404];
bool dp[202][202];
int main(){
	int n;

	cin >> n;
	int co = 1;
	while(n--){
		memset(dp, 0, sizeof(dp));
		scanf("%s%s%s",a,b,c);
		int alen = strlen(a);
		int blen = strlen(b);
		if(a[0] == c[0])dp[1][0] = true;
		if(b[0] == c[0])dp[0][1] = true;
		for(int i = 2;i <= alen;i++){
			if(a[i-1] == c[i-1] && dp[i-1][0] == true)dp[i][0] = true;	
		}
		for(int i = 2;i <= blen;i++){
			if(b[i-1] == c[i-1] && dp[0][i-1] == true)dp[0][i] = true;
		}
		for(int i = 1;i <= alen;i++){
			for(int j = 1;j <= blen;j++){
				if(a[i-1] == c[i+j-1] && dp[i-1][j] == true){
					dp[i][j] = true;
				}else if(b[j-1] == c[i+j-1] && dp[i][j-1] == true){
					dp[i][j] = true;
				}
			}
		}
		if(dp[alen][blen] == true){
			printf("Data set %d: yes
",co);
		}else{
			printf("Data set %d: no
",co);
		}
		co++;
	}

	return 0;

}