首页 > 代码库 > BZOJ1055: [HAOI2008]玩具取名

BZOJ1055: [HAOI2008]玩具取名

2024-07-21 14:23:39   222人阅读

1055: [HAOI2008]玩具取名

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 820  Solved: 482
[Submit][Status]

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 [数据范围] 30%数据满足Len<=20，W、I、N、G<=6 100%数据满足Len<=200，W、I、N、G<=16

 

Source

题解：

真是一道巧妙的DP！！！

OI不是考你会不会什么算法，而是看你能不能想到。真正的大牛不会因为不会码什么而不会做什么题，什么算法都随便写，只要想到。。。

这题如果有DP的想法就很简单了，dp[i][j][k]表示从 i 到 j 能否变成 k，然后就很好转移了。

OI就应该多考这种思路巧妙而代码量又不大的题目！！！

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 300+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 const char t[5]={‘ ‘,‘W‘,‘I‘,‘N‘,‘G‘};23 inline int read()24 {25     int x=0,f=1;char ch=getchar();26     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}27     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}28     return x*f;29 }30 vector<int> a[5][5];31 int num[5],n,ans;32 bool dp[maxn][maxn][5];33 string s;34 inline int hash(char ch)35 {36     if(ch==‘W‘)return 1;37     if(ch==‘I‘)return 2;38     if(ch==‘N‘)return 3;39     if(ch==‘G‘)return 4;    40 }41 int main()42 {43     freopen("input.txt","r",stdin);44     freopen("output.txt","w",stdout);45     for1(i,4)num[i]=read();46     for1(i,4)47      for1(j,num[i])48       {49           cin>>s;50           a[hash(s[0])][hash(s[1])].push_back(i);51       }52     cin>>s;53     n=s.length();54     for1(i,n)dp[i][i][hash(s[i-1])]=1;  55     for2(l,2,n)56      for1(i,n-l+1)57       {58           int j=i+l-1;59           for2(k,i,j-1)60           for1(p,4)61            if(dp[i][k][p])62             for1(q,4)63              if(dp[k+1][j][q])64               for(int w=0;w<a[p][q].size();w++)65                dp[i][j][a[p][q][w]]=1;66       }67     ans=0;68     for1(i,4)if(dp[1][n][i])ans++,cout<<t[i];69     if(!ans)puts("The name is wrong!");  70     return 0;71 }
View Code

 

BZOJ1055: [HAOI2008]玩具取名


联系
我们