[LUOGU] P4290 [BZOJ] 1055 [HAOI2008]玩具取名

题目描述

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。

现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

输入输出格式

输入格式：

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。

接下来W行，每行两个字母,表示W可以用这两个字母替代。

接下来I行，每行两个字母,表示I可以用这两个字母替代。

接下来N行，每行两个字母,表示N可以用这两个字母替代。

接下来G行，每行两个字母,表示G可以用这两个字母替代。

最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

输出格式：

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）

如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

输入输出样例

输入样例#1：

1 1 1 1

II

WW

WW

IG

IIII

输出样例#1：

IN

说明

30%数据满足Len<=20，W、I、N、G<=6

100%数据满足Len<=200，W、I、N、G<=16

提示是区间DP，倒着思考，从最终答案想状态定义，大概形如4个布尔f[i][j] 表示[i,j]能不能变成[1/2/3/4]（对应WING）

枚举切开区间的点k，看[i,k]和[k+1,j]所有可能的组合能否合成一个点，对于判断用的dfs函数，就看能否拼成所需的点x，能就返回1

缩点思想。

//Stay foolish,stay hungry,stay young,stay simple

#include<cstdio>

#include<iostream>

#include<cstring>

#define R register

using namespace std;

int cti[300];

inline int read_d(){

    int s=0;

    char c;

    while(c=getchar(),c<'0'||c>'9');

    while(c<='9'&&c>='0'){

        s=s*10+c-'0';

        c=getchar();

    }

    return s;

}

int num[5];

int mat[5][20],cnt[5];

char s[202];

bool f[202][202][5];

bool vis[202][202][5];

int dfs(int l,int r,int x){

    bool &ans=f[l][r][x];

    if(vis[l][r][x]) return ans;

    vis[l][r][x]=1;

    for(int k=l;k<r;k++){//every k cut up the line into two

        for(int i=1;i<=4;i++){

            for(int j=1;j<=4;j++){

                if((!dfs(l,k,i))||(!dfs(k+1,r,j)))

                    continue;//here i and j are available

                int *p=&mat[x][0];

                for(int q=1;q<=cnt[x];q++)

                    if(*(p+q)==i*10+j)//judge if (i,j) can be x

                        return ans=1;

            }

        }

    }

    return 0;

}

int main(){

    cti['W']=1;cti['I']=2;

    cti['N']=3;cti['G']=4;

    for(R int i=1;i<=4;i++)

        num[i]=read_d();

    for(R int i=1;i<=4;i++){

        for(R int j=1;j<=num[i];j++){

            char x[4];

            scanf("%s",x);

            mat[i][++cnt[i]]=cti[x[0]]*10+cti[x[1]];

        }

    }

    scanf("%s",s+1);

    int lens=strlen(s+1);

    for(R int i=1;i<=lens;i++){

        f[i][i][cti[s[i]]]=1;

        bool *p=&vis[i][i][1];

        *p=*(p+1)=*(p+2)=*(p+3)=1;

    }

    bool succ=0;

    if(dfs(1,lens,1)) putchar('W'),succ=1;

    if(dfs(1,lens,2)) putchar('I'),succ=1;

    if(dfs(1,lens,3)) putchar('N'),succ=1;

    if(dfs(1,lens,4)) putchar('G'),succ=1;

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

    return 0;

}

巴特西

[LUOGU] P4290 [BZOJ] 1055 [HAOI2008]玩具取名

最新文章

热门文章