【bzoj1055】[HAOI2008]玩具取名

2015.05.25 19:59 Mon | 6次阅读 | 旧日oi | 固定链接 | 源码

Description

某人有一套玩具,并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好,将名字中任意一个字母用“WING”中任意两个字母代替,使得自己的名字能够扩充得很长。现在,他想请你猜猜某一个很长的名字,最初可能是由哪几个字母变形过来的。

Input

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行,每行两个字母,表示W可以用这两个字母替代。接下来I行,每行两个字母,表示I可以用这两个字母替代。接下来N行,每行两个字母,表示N可以用这两个字母替代。接下来G行,每行两个字母,表示G可以用这两个字母替代。最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

Output

一行字符串,该名字可能由哪些字母变形而得到。(按照WING的顺序输出)如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

Sample Input

1 1 1 1
II
WW
WW
IG
IIII

Sample Output

IN

HINT

W可以变成II所以IIII可以缩成WW IN均能变成WW所以WW又可以缩成I或者N 所以最终答案应该按照“WING”的顺序输出IN
[数据范围]
100%数据满足Len<=200,W、I、N、G<=16

题解

这题写的好爽,各种复制粘贴……
dp[i][j][k]表示从第i个到第j个能否变成k,然后就没什么了

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int dp[205][205][4];
int W,I,N,G,len;
map<char,int> mp;
char s[10],str[205];
int v[4][100];
int main()
{
    cin>>W>>I>>N>>G;
    mp['W']=0;mp['I']=1;mp['N']=2;mp['G']=3;
    for(int tmp,i=1;i<=W;i++) 
    {
        scanf("%s",s);
        tmp=mp[s[0]]*10+mp[s[1]];
        v[0][tmp]=1;
    }
    for(int tmp,i=1;i<=I;i++) 
    {
        scanf("%s",s);
        tmp=mp[s[0]]*10+mp[s[1]];
        v[1][tmp]=1;
    }
    for(int tmp,i=1;i<=N;i++) 
    {
        scanf("%s",s);
        tmp=mp[s[0]]*10+mp[s[1]];
        v[2][tmp]=1;
    }
    for(int tmp,i=1;i<=G;i++) 
    {
        scanf("%s",s);
        tmp=mp[s[0]]*10+mp[s[1]];
        v[3][tmp]=1;
    }
    scanf("%s",str+1);len=strlen(str+1);
    for(int i=1;i<=len;i++) dp[i][i][mp[str[i]]]=1;
    for(int k=1;k<len;k++)
    for(int i=1;i+k<=len;i++)
    {
        for(int j=i+1;j<=i+k;j++)
        {
            for(int p=0;p<4;p++)
            if(dp[i][j-1][p])
            {
                for(int tmp,q=0;q<4;q++)
                if(dp[j][i+k][q])
                {
                    tmp=10*p+q;
                    if(v[0][tmp]) dp[i][i+k][0]=1;
                    if(v[1][tmp]) dp[i][i+k][1]=1;
                    if(v[2][tmp]) dp[i][i+k][2]=1;
                    if(v[3][tmp]) dp[i][i+k][3]=1;
                }
            }
        }
    }
    bool flag=0;
    if(dp[1][len][0]) flag=1,printf("W");
    if(dp[1][len][1]) flag=1,printf("I");
    if(dp[1][len][2]) flag=1,printf("N");
    if(dp[1][len][3]) flag=1,printf("G");
    if(!flag) puts("The name is wrong!");
}```