CodeDevil

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1055

【题意】

四个字母'W' 'I' 'N' 'G'，每个都可以转换成另两个字母(都是由'W' 'I' 'N' 'G'构成)。

现给定一个由'W' 'I' 'N' 'G'构成的字符串，问最开始可能由哪些字母变形得到。按'W' 'I' 'N' 'G'的优先级输出。

【题解】

区间DP，我居然看了半天不会做。。。找了篇题解才搞懂 （果然还是太弱了QAQ）

dp[l][r][x]表示现有的串l~r这一区间能否由字母x转换得到

设字母x可变换成的两个字母是a和b，那么dp[l][j][a]和dp[j+1][r][b]均为true时，dp[l][r][x]才为true

【代码】

#include<iostream>

#include<cstdio>

#include<cstring>

#include <string>

using namespace std;

string str;

char a[4][20][2];

int dp[210][210][4],sum[4];

char Char(int c)

{

    if (c==0) return 'W';

    if (c==1) return 'I';

    if (c==2) return 'N';

    return 'G';

}

 

int Num(char c)

{

    if (c=='W') return 0;

    if (c=='I') return 1;

    if (c=='N') return 2;

    return 3;

}

 

bool check(int l,int r,int x)

{

    if (dp[l][r][x]!=-1) return dp[l][r][x];

    int i,j;

    if (l==r)

        if (str[l]==Char(x)) 

            return true;

        else

            return false;

    for (i=1;i<=sum[x];i++)

        for (j=l;j<=r-1;j++)

            if (check(l,j,Num(a[x][i][0])) && check(j+1,r,Num(a[x][i][1])))

                return dp[l][r][x]=true;

    return dp[l][r][x]=false;

}

 

int main()

{

    int i,j;

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

        scanf("%d",&sum[i]);

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

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

            scanf("%s",a[i][j]);

    cin>>str;

    bool flag=0;

    memset(dp,-1,sizeof(dp));

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

        if (check(0,str.length()-1,i))

        {

            flag=true;

            cout<<Char(i);

        }

    if (!flag)

        cout<<"The name is wrong!"<<endl;

    return 0;

}