题解 P4290 【[HAOI2008]玩具取名】

狄凡人 · 2019-03-12 21:52:49 · 题解

第一篇题解，望各位大佬支持，谢谢

首先面对这道题，我的第一个困难是怎么读入数据QWQ 首先说明一下变量的含义：

bool dp[maxn][maxn][5],can[5][5][5];//f[i j k]表示区间 i,j由 k转化.can[ i j k]表示i可以由j、k转化
int q[5],len=0;//q是每个字母转化成几对字母
char s[maxn];//原名字
int change(char i)//把字母转化成数字
{  
    if(i=='W') return 1; 
    if(i=='I') return 2;
    if(i=='N') return 3; 
    if(i=='G') return 4; 
} 

再同学们的帮助下，历经了两天晚自习，我成功的读入了数据

int main() {
    for(int i=1;i<=4;i++) scanf("%d",&q[i]);//有几对字母可以转化
    for(int i=1;i<=4;i++) 
    {
        for(int j=1;j<=q[i];j++) 
        {
            scanf("%s",&c);//直接读到空格或者回车结束
            can[i][change(c[0])][change(c[1])]=true;//第一个字母可以由二、三个转化过来
        }
    }

    scanf("%s",s+1); //从s+1开始读入
    for(len=1;s[len];len++);//只要没结束，就继续读
    len--;//会多一个，所以--

接下来才是解读： 这是一道标准的区间DP，原因很简单，要把它分区间求解，并且之前处理的结果会对之后产生影响，具体问题见注释

for(int i=1;i<=len;i++) dp[i][i][change(s[i])]=true;//从i到i可以由他自己转化

    for(int led=1;led<len;led++)//列举长度的可能性
        for(int l=1;l<=len-led;l++)//列举左界的可能性 
        {
            int r=l+led;//右界可以算出来
            for(int k=l;k<r;k++) //在左右之间列举可能的断点 
                for(int z=1;z<=4;z++)  //列举l到r（需要的区间）可能转化成的字母
                    for(int z1=1;z1<=4;z1++) // 列举l到k（借助的左区间）
                        for(int z2=1;z2<=4;z2++)  //列举k + 1到r（借助的右区间）
                            if(can[z][z1][z2] && dp[l][k][z1] && dp[k+1][r][z2]) 
//如果z1、z2可以转化成z 并且 l到k可以变成z1 并且k+1到r可以变成z2
                                dp[l][r][z]=true;
//那么l到r就可以转化成z
        }

输出也很简单，只需要查询1~len可不可以被四个字母取代

bool f=false;
    if(dp[1][len][1]) {f=true;printf("W");}
    if(dp[1][len][2]) {f=true;printf("I");}
    if(dp[1][len][3]) {f=true;printf("N");}
    if(dp[1][len][4]) {f=true;printf("G");}
    if(!f) printf("The name is wrong!");

那么... 附AC代码，如有意见欢迎私信本蒟蒻

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn =210;
bool dp[maxn][maxn][5],can[5][5][5];//f[i j k]表示区间 i,j由 k转化.
int q[5],len=0;
char s[maxn];
int change(char i){  
    if(i=='W') return 1; 
    if(i=='I') return 2;
    if(i=='N') return 3; 
    if(i=='G') return 4; 
} 
int main() {
    for(int i=1;i<=4;i++) scanf("%d",&q[i]);
    for(int i=1;i<=4;i++) 
    {
        for(int j=1;j<=q[i];j++) 
        {
            scanf("%s",&c);
            can[i][change(c[0])][change(c[1])]=true;
        }
    }

    scanf("%s",s+1); 
    for(len=1;s[len];len++);
    len--;
    for(int i=1;i<=len;i++) dp[i][i][change(s[i])]=true;

    for(int led=1;led<len;led++)//列举长度 
        for(int l=1;l<=len-led;l++)//列举左界 
        {
            int r=l+led;
            for(int k=l;k<r;k++) //列举断点 
                for(int z=1;z<=4;z++)  //列举l到r
                    for(int z1=1;z1<=4;z1++) // 列举l到k
                        for(int z2=1;z2<=4;z2++)  //列举k + 1到r
                            if(can[z][z1][z2] && dp[l][k][z1] && dp[k+1][r][z2]) 
                                dp[l][r][z]=true;
        }
    bool f=false;
    if(dp[1][len][1]) {f=true;printf("W");}
    if(dp[1][len][2]) {f=true;printf("I");}
    if(dp[1][len][3]) {f=true;printf("N");}
    if(dp[1][len][4]) {f=true;printf("G");}
    if(!f) printf("The name is wrong!");
    return 0;
}