1055: [HAOI2008]玩具取名

题目：传送门

简要题意：

　　　　就是固定四个字母，给出这四个字母分别可以由哪两个字母组成，然后在给你一个字符串，要求把这个字符串还原成原始的四个字母的其中一个。

题解：

　　一开始看题有点瞎...想了想是一道超级大难题...

　　其实就是一个很简单的DP...

　　定义发f[i][j][s]:表示在字符串中i~j这个区间是否可以组合成为字符s

　　转移很容易就可以想出来：因为如果f[i][k][s1]==f[k+1][j][s2]==1(i<=k<=j) && s1和s2可以组成s，那么f[i][j][s]=1;

　　 O(n^4)...大水题

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 char s[];

 struct node

 {

     char s1,s2,id;

 }st[];

 bool f[][][];

 int main()

 {

     int W,I,N,G;bool bk=false;

     scanf("%d%d%d%d",&W,&I,&N,&G);

     int len=;

     for(int i=;i<=W;i++)

         scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='W';

     for(int i=;i<=I;i++)

         scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='I';

     for(int i=;i<=N;i++)

         scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='N';

     for(int i=;i<=G;i++)

         scanf("%s",s+),st[++len].s1=s[],st[len].s2=s[],st[len].id='G';

     scanf("%s",s+);

     int len1=strlen(s+);

     memset(f,,sizeof(f));

     for(int i=;i<=len1;i++)f[i][i][s[i]]=true;

     for(int i=;i<=len1;i++)//长度

         for(int l=;l<=len1-i+;l++)//左端点

         {

             int r=l+i-;

             for(int j=l;j<=r;j++)//断点

                 for(int k=;k<=len;k++)//枚举所有种类的字符串

                     if(f[l][j][st[k].s1] && f[j+][r][st[k].s2])

                         f[l][r][st[k].id]=true;

         }

     W='W';I='I';N='N';G='G';

     if(f[][len1][W])printf("W"),bk=true;

     if(f[][len1][I])printf("I"),bk=true;

     if(f[][len1][N])printf("N"),bk=true;

     if(f[][len1][G])printf("G"),bk=true;

     if(bk==false)printf("The name is wrong!\n");

     return ;

 }

巴特西

bzoj1055: [HAOI2008]玩具取名（dp）

1055: [HAOI2008]玩具取名

最新文章

热门文章