时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。 输入描述:
第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。 接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。 接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。 最后一行一个长度不超过Len的字符串。表示这个玩具的名字。
输出描述:
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出） 如果给的名字不能由任何一个字母变形而得到则输出“The name
is wrong!”
示例1
输入
1 1 1 1
II
WW
WW
IG
IIII
输出
IN
题解
题目虽然输入的是字母，但是我们可以当做数字来处理
重要的两个数组，均为bool型
dp[i][j][k]表示区间[i,j]是否是由k转化而来的
can[i][j][k]表示i是否可以用 j k 两个字母代替
can是在读入时更新
我们想一想区间更新的条件：
区间[l,r],中间点为k
z，z1，z2为1~4，表示为WING
如果左区间[l,k+1]可以由z1转化（即代码dp[l][k][z1]），右区间[k+1,r]可以由z2转化(代码dp[k+1][r][z2]),
z可以用z1和z2来代替（代码dp[z][z1][z2]），那是不是就说明区间[l,r]是由z转化的
（相当于z1，z2是一个中转站，用来将区间[l,r]与z联系在一起）
套上区间dp的万能模板
就能得到
for(int i=1;i<=len;i++) dp[i][i][a[i]]=true;//从i到i可以由他自己转化
for(int led=1;led<len;led++)//列举长度的可能性
for(int l=1;l<=len-led;l++)//列举左界的可能性
{
int r=l+led;//右界可以算出来
for(int k=l;k<r;k++) //在左右之间列举可能的断点
for(int z=1;z<=4;z++) //列举l到r（需要的区间）可能转化成的字母
for(int z1=1;z1<=4;z1++) // 列举l到k（借助的左区间）
for(int z2=1;z2<=4;z2++) //列举k + 1到r（借助的右区间）
if(can[z][z1][z2] && dp[l][k][z1] && dp[k+1][r][z2])
//如果z1、z2可以转化成z 并且 l到k可以变成z1 并且k+1到r可以变成z2
dp[l][r][z]=true;
//那么l到r就可以转化成z
}
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e2+7;
int dp[maxn][maxn][maxn];
bool can[maxn][maxn][maxn];
int p[maxn];
char s[maxn];
int a[300];
int change(char i){
if(i=='W') return 1;
if(i=='I') return 2;
if(i=='N') return 3;
if(i=='G') return 4;
}
int main()
{
a['W']=1;
a['I']=2;
a['N']=3;
a['G']=4;
for(int i=1;i<=4;i++)cin>>p[i];
for(int i=1;i<=4;i++)
{
for(int j=1;j<=p[i];j++)
{
char x,y;
cin>>x>>y;
can[i][a[x]][a[y]]=1;
}
}
cin>>(s+1);
int n=strlen(s+1);
// cout<<n<<endl;
for(int i=1;i<=n;i++)dp[i][i][a[s[i]]]=1;
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n;i++)
{
int j=i+len-1;
if(j>n)break;
for(int k=i;k<=j;k++)
{
for(int z=1;z<=4;z++)
{
for(int z1=1;z1<=4;z1++)
{
for(int z2=1;z2<=4;z2++)
{
if(can[z][z1][z2]&&dp[i][k][z1]&&dp[k+1][j][z2])
dp[i][j][z]=1;
}
}
}
}
}
}
bool flag=false;
if(dp[1][n][1]) {
flag=true;printf("W");}
if(dp[1][n][2]) {
flag=true;printf("I");}
if(dp[1][n][3]) {
flag=true;printf("N");}
if(dp[1][n][4]) {
flag=true;printf("G");}
if(!flag) printf("The name is wrong!");
}
京公网安备 11010502036488号