【BZOJ1055】[HAOI2008]玩具取名（动态规划）

题面

BZOJ

洛谷

题解

裸的区间\(dp\)，设\(f[i][j][W/I/N/G]\)表示区间\([i,j]\)能否由某个字母替换过来，转移的时候枚举用哪一个变换即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

#define MAX 222

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

map<char,int> M;

char str[]="WING",s[MAX],ch[MAX];

int p[100][3],tot;

bool f[MAX][MAX][4];

int a[4],n,ans;

int main()

{

	for(int i=0;i<4;++i)a[i]=read();

	for(int i=0;i<4;++i)M[str[i]]=i;

	for(int i=0;i<4;++i)

		for(int j=1;j<=a[i];++j)

		{

			scanf("%s",ch+1);++tot;

			p[tot][0]=M[ch[1]];

			p[tot][1]=M[ch[2]];

			p[tot][2]=M[str[i]];

		}

	scanf("%s",s+1);n=strlen(s+1);

	for(int i=1;i<=n;++i)f[i][i][M[s[i]]]=true;

	for(int l=1;l<=n;++l)

		for(int i=1,j=i+l-1;j<=n;++i,++j)

			for(int k=i;k<j;++k)

				for(int x=1;x<=tot;++x)

					f[i][j][p[x][2]]|=f[i][k][p[x][0]]&f[k+1][j][p[x][1]];

	for(int i=0;i<4;++i)if(f[1][n][i])putchar(str[i]),++ans;

	if(ans)puts("");else puts("The name is wrong!");

	return 0;

}