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

小咪咪 2021-09-29 02:50 202阅读 0赞

题目描述
    某人有一套玩具，并想法给玩具命名。首先他选择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;
    }

转载于:https://www.cnblogs.com/ghostcai/p/9247461.html