[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 1

II

WW

WW

IG

IIII

输出样例#1：

IN

说明

$30\%$数据满足$Len<=20，W、I、N、G<=6$

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

题解

这道题比之前做的一道类似模拟题要简单。。。

存储稍微麻烦一点的区间DP。

$i$到$k$有前一个字符，$k+1$到$j$有后一个字符，那么就可以由一个对应的字符合成。

$if(dp[i][k][a[h][o][1]]\&\&dp[k+1][j][a[h][o][2]])$ $dp[i][j][h]=1; $

为了方便，我们把$W,I,N,G$转换为$1,2,3,4$。

code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#define R register

#define ll long long

using namespace std;

template<typename T>inline void read(T &a){

    char c=getchar();T x=0,f=1;

    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}

    a=f*x;

}

int c[5],a[5][20][3],n,dp[205][205][5],flg;

char ch[5],s[205];

inline int num(R char x){

    if(x=='W')return 1;

    if(x=='I')return 2;

    if(x=='N')return 3;

    if(x=='G')return 4;

}

inline char cha(R int x){

    if(x==1)return 'W';

    if(x==2)return 'I';

    if(x==3)return 'N';

    if(x==4)return 'G';

}

int main(){

    for(R int i=1;i<=4;i++)read(c[i]);

    for(R int i=1;i<=4;i++){

        for(R int j=1;j<=c[i];j++){

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

            a[i][j][1]=num(ch[1]);

            a[i][j][2]=num(ch[2]);

        }

    }

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

    n=strlen(s+1);

    for(R int i=1;i<=n;i++)

        dp[i][i][num(s[i])]=1;

    for(R int l=2;l<=n;l++){

        for(R int i=1;i<=n-l+1;i++){

            R int j=i+l-1;

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

                for(R int h=1;h<=4;h++){

                    for(R int o=1;o<=c[h];o++){

                        if(dp[i][k][a[h][o][1]]&&dp[k+1][j][a[h][o][2]])

                            dp[i][j][h]=1;

                    }

                }

            }

        }

    }

    for(R int i=1;i<=4;i++)

        if(dp[1][n][i])cout<<cha(i),flg=1;

    if(!flg)printf("The name is wrong!\n");

    return 0;

}

巴特西

【BZOJ1055】[HAOI2008]玩具取名（区间DP）