[bzoj1055][HAOI2008]玩具取名

玩具取名 bzoj-1055 HAOI-2008

题目大意：给你一个用W，I，N，G组成的字符串，给你一些这四个字符之间的变换规则，每一个变换规则都是由一个字符变成两个字符，问这个字符串是否可能是由一个单独的字符变成的。

注释：$1\le Len\le 200$，每种字符的变换规则<=16

想法：刚看见题以为又是什么单词接龙之类的题，然后看了一眼数据范围... ...还是不会。

查了题解，发现是一个挺不常见的bool区间dp

状态：dp[i][j][c]表示[i,j]这段区间是否能变成c字符，c是W，I，N，G中的一个。

转移：dp[i][j][c]=dp[i][k][c1]|dp[k+1][j][c2]&&c1和c2能合成c。

时间复杂度：$O(Len^3\cdot 16)$。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

#define MAXN 205

int W,I,N,G,n,cnt;

char s[MAXN];

struct hp{char x,y,z;}ch[MAXN];

bool f[MAXN][MAXN][100];

int main()

{

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

    for (int i=1;i<=W;++i) gets(s),ch[++cnt].x=s[0],ch[cnt].y=s[1],ch[cnt].z='W';

    for (int i=1;i<=I;++i) gets(s),ch[++cnt].x=s[0],ch[cnt].y=s[1],ch[cnt].z='I';

    for (int i=1;i<=N;++i) gets(s),ch[++cnt].x=s[0],ch[cnt].y=s[1],ch[cnt].z='N';

    for (int i=1;i<=G;++i) gets(s),ch[++cnt].x=s[0],ch[cnt].y=s[1],ch[cnt].z='G';

    gets(s);n=strlen(s);

    for (int i=n;i>=1;--i) s[i]=s[i-1];

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

    for (int len=2;len<=n;++len)

        for (int l=1;l<=n-len+1;++l)

        {

            int r=l+len-1;

            for (int k=l;k<=r;++k)

                for (int i=1;i<=cnt;++i)

                    f[l][r][ch[i].z]|=f[l][k][ch[i].x]&&f[k+1][r][ch[i].y];

        }

    bool flag=false;

    if (f[1][n]['W']) putchar('W'),flag=true;

    if (f[1][n]['I']) putchar('I'),flag=true;

    if (f[1][n]['N']) putchar('N'),flag=true;

    if (f[1][n]['G']) putchar('G'),flag=true;

    if (!flag) puts("The name is wrong!");

    else putchar('\n');

}

小结：有的时候从数据范围入手猜时间复杂度，从时间复杂度入手解题，是很方便的。

巴特西

[bzoj1055][HAOI2008]玩具取名_区间dp

最新文章

热门文章