[BZOJ1055][HAOI2008]玩具取名

试题描述

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

输入

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两个字母替代。接下来I行，每行两个字母,表示I可以用这两个字母替代。接下来N行，每行两个字母,表示N可以用这两个字母替代。接下来G行，每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

输出

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

输入示例

1 1 1 1
II
WW
WW
IG
IIII

输出示例

IN

数据规模及约定

100%数据满足Len<=200，W、I、N、G<=16

题解

一个字母变成字符串直接处理起来似乎挺麻烦，考虑把串一步步缩成一个字母，设计一个 dp，f[i][j][k] 表示 S_i~j 是否能合并成字母 k。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;

int read() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

#define maxn 210
#define maxt 20
int has[4];
bool f[maxn][maxn][4];
char Str[4][maxt][2], S[maxn];

int main() {
	for(int i = 0; i < 4; i++) has[i] = read();
	for(int i = 0; i < 4; i++)
		for(int j = 1; j <= has[i]; j++) {
			scanf("%s", Str[i][j]);
			for(int k = 0; k < 2; k++) {
				if(Str[i][j][k] == 'W') Str[i][j][k] = 0;
				if(Str[i][j][k] == 'I') Str[i][j][k] = 1;
				if(Str[i][j][k] == 'N') Str[i][j][k] = 2;
				if(Str[i][j][k] == 'G') Str[i][j][k] = 3;
			}
		}
	scanf("%s", S);
	
	int n = strlen(S);
	for(int i = 0; i < n; i++) {
		if(S[i] == 'W') S[i] = 0;
		if(S[i] == 'I') S[i] = 1;
		if(S[i] == 'N') S[i] = 2;
		if(S[i] == 'G') S[i] = 3;
		f[i][i][S[i]] = 1;
	}
	for(int len = 2; len <= n; len++)
		for(int i = 0; i + len - 1 < n; i++) {
			int j = i + len - 1;
//			printf("%d %d
", i, j);
			for(int k = 0; k < 4; k++) if(!f[i][j][k])
				for(int m = i; m < j; m++) {
					for(int l = 1; l <= has[k]; l++) if(f[i][m][Str[k][l][0]] & f[m+1][j][Str[k][l][1]]) {
						f[i][j][k] = 1; break;
					}
					if(f[i][j][k]) break;
				}
		}
	
	bool ok = 0;
	for(int i = 0; i < 4; i++) if(f[0][n-1][i]) {
		if(i == 0) putchar('W');
		if(i == 1) putchar('I');
		if(i == 2) putchar('N');
		if(i == 3) putchar('G');
		ok = 1;
	}
	if(!ok) puts("The name is wrong!");
	else putchar('
');
	
	return 0;
}