[BZOJ1055][HAOI2008]玩具取名 区间DP


原题链接
告诉你WING四个字母各能分裂成哪两个字母,然后给你一个字符串,问它可能是哪几个字符分裂成的.
区间DP嘛...来一波状压和记忆化搜索操作可以好写一些.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 233
using namespace std;
int len,num[4],f[1<<8],g[1<<4][1<<4],a[N],dp[N][N];//f[s]表示s这两个字符能合成啥,g[i][j]表示i和j这两个合并状态再合并能合并成啥
inline int getid(char c)
{
    if(c=='W')return 0;
    if(c=='I')return 1;
    if(c=='N')return 2;
    if(c=='G')return 3;
    return -1;
}
char str[N];
inline int merge(int s1,int s2)
{
    int i,j,s,re=0;
    for(i=0;i<4;++i)if(s1&(1<<i))
    {
        for(j=0;j<4;++j)if(s2&(1<<j))
        {
            s=(1<<i)|(1<<(j+4));
            re|=f[s];
        }
    }
    return re;
}
int v[N][N];
int dfs(int l,int r)
{
    if(v[l][r])return dp[l][r];
    v[l][r]=1;
    if(l==r)return dp[l][r]=1<<a[l];
    int i;
    for(i=l;i<r;++i)dp[l][r]|=g[dfs(l,i)][dfs(i+1,r)];
    return dp[l][r];
}
int main()
{
    int i,j,s;
    char flag[5];
    for(i=0;i<4;++i)scanf("%d",&num[i]);
    for(i=0;i<4;++i)
    {
        for(j=1;j<=num[i];++j)
        {
            s=0;
            scanf("%s",flag);
            s|=1<<getid(flag[0]),s|=1<<(getid(flag[1])+4);
            f[s]|=1<<i;
        }
    }
    scanf("%s",str+1);
    len=strlen(str+1);
    for(i=1;i<=len;++i)a[i]=getid(str[i]);
    for(i=0;i<16;++i)
    {
        for(j=0;j<16;++j)g[i][j]=merge(i,j);
    }
    s=dfs(1,len);
    if(!s)puts("The name is wrong!");
    else
    {
        if(s&1)putchar('W');
        if(s&(1<<1))putchar('I');
        if(s&(1<<2))putchar('N');
        if(s&(1<<3))putchar('G');       
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注