Description
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
Input
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
Output
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”
这题切了emmm
区间dp
好题.
就是卡我智商。感觉复杂度不太对,但是过了emmm。
我们设(ok[i][0])代表第(i)个变化方式的原字符.
且(ok[i][0])只会是('W' 'I' 'N' 'G')
(ok[i][1])存储变化后的第一个字符,(ok[i][2])存储变化后的第二个字符.
然后设(f[i][j][k])代表(i)到(j)这一段区间能否变成(k)这个字符.
表示刚开始读错题了
输出可能变成的即可.
然后判断无解的话,就是判断前面是否有过输出.
区间DP的一般套路.
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int W,I,N,G,tot;
char s[10],str[208];
int ok[208][3];
bool f[208][208][5],flg;
inline int rep(char s)
{
if(s=='W')return 1;
if(s=='I')return 2;
if(s=='N')return 3;
if(s=='G')return 4;
}
int main()
{
in(W),in(I),in(N),in(G);
for(R int i=1;i<=W;i++)
{
scanf("%s",s+1);
ok[++tot][0]=1;
ok[tot][1]=rep(s[1]);
ok[tot][2]=rep(s[2]);
}
for(R int i=1;i<=I;i++)
{
scanf("%s",s+1);
ok[++tot][0]=2;
ok[tot][1]=rep(s[1]);
ok[tot][2]=rep(s[2]);
}
for(R int i=1;i<=N;i++)
{
scanf("%s",s+1);
ok[++tot][0]=3;
ok[tot][1]=rep(s[1]);
ok[tot][2]=rep(s[2]);
}
for(R int i=1;i<=G;i++)
{
scanf("%s",s+1);
ok[++tot][0]=4;
ok[tot][1]=rep(s[1]);
ok[tot][2]=rep(s[2]);
}
scanf("%s",str+1);
int len=strlen(str+1);
for(R int i=1;i<=len;i++)
f[i][i][rep(str[i])]=true;
for(R int i=len;i>=1;i--)
for(R int j=i+1;j<=len;j++)
for(R int k=i;k<j;k++)
for(R int now=1;now<=tot;now++)
if(f[i][k][ok[now][1]] and f[k+1][j][ok[now][2]])
f[i][j][ok[now][0]]=true;
if(f[1][len][1])putchar('W'),flg=true;
if(f[1][len][2])putchar('I'),flg=true;
if(f[1][len][3])putchar('N'),flg=true;
if(f[1][len][4])putchar('G'),flg=true;
if(!flg)puts("The name is wrong!");
}