BZOJ 1055 HAOI2008 玩具命名

1055: [HAOI2008]玩具取名

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2141  Solved: 1254
[Submit][Status][Discuss]
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

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
设f[i][j][k]表示从i到j是否可以表示为k
按照题目给的条件转移即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int f[210][210][5];
 4 int a[5][20][2];
 5 int sum[5],strl;
 6 inline int dp(int leftt,int rightt,int k){
 7     if(f[leftt][rightt][k]!=-1) return f[leftt][rightt][k];
 8     f[leftt][rightt][k]=0;
 9     for(int i=1;i<=sum[k];i++){
10         for(int j=leftt;j<rightt;j++){
11             if(dp(leftt,j,a[k][i][1])&&dp(j+1,rightt,a[k][i][2])) f[leftt][rightt][k]=1;
12         }
13     }
14     return f[leftt][rightt][k];
15 }
16 void init(){
17     for(int i=1;i<=4;i++){
18         cin>>sum[i];
19     }
20     for(int i=1;i<=4;i++){
21         for(int j=1;j<=sum[i];j++){
22             char ch[5];
23             scanf("%s",ch);
24             if(ch[0]=='W') a[i][j][1]=1;
25             if(ch[0]=='I') a[i][j][1]=2;
26             if(ch[0]=='N') a[i][j][1]=3;
27             if(ch[0]=='G') a[i][j][1]=4;
28             if(ch[1]=='W') a[i][j][2]=1;
29             if(ch[1]=='I') a[i][j][2]=2;
30             if(ch[1]=='N') a[i][j][2]=3;
31             if(ch[1]=='G') a[i][j][2]=4; 
32         }
33     }
34     memset(f,-1,sizeof(f));
35     string str;
36     cin>>str;
37     strl=str.size();
38     for(int i=0;i<strl;i++){
39         for(int j=1;j<=4;j++){
40             f[i+1][i+1][j+1]=0;
41         }
42         if(str[i]=='W') f[i+1][i+1][1]=1;
43         if(str[i]=='I') f[i+1][i+1][2]=1;
44         if(str[i]=='N') f[i+1][i+1][3]=1;
45         if(str[i]=='G') f[i+1][i+1][4]=1;
46     }
47 }
48 void solve(){
49     int flag=0;
50     for(int i=1;i<=4;i++){
51         if(dp(1,strl,i)){
52             if(i==1) cout<<"W";
53             if(i==2) cout<<"I";
54             if(i==3) cout<<"N";
55             if(i==4) cout<<"G";
56             flag=1; 
57         }
58     }
59     if(!flag) cout<<"The name is wrong!"<<endl;
60 }
61 int main(){
62     init();
63     solve();
64     return 0;
65 }

代码