[HAOI2008]玩具取名

标签：动态规划 区间DP

---

题目描述

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

Hint

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

题解

题意是由一个字母变成一段字母区间，问这个字母是什么。那我们不妨反过来思考，这一段区间能否变成一个字母。状态也就随之而来了。
f[i][j][k]表示[i,j]这段区间是否可以合成k这个字符。
转移肯定采用区间合并法。
小trick：在读入的是否我们可以用一个g[i][j][k]数组表示i字符和j字符能否组成k字符。
转移方程：

for(int k = i; k < j; k ++) //枚举断点
    for(int a = 1; a <= 4; a ++) //枚举字符
        for(int b = 1; b <= 4; b ++) //枚举字符
            for(int c = 1; c <= 4; c ++) //枚举字符
                if(g[a][b][c] && f[i][k][b] && f[k + 1][j][c]) //如果全部合法，则可以转移
                  f[i][j][a] = true;

代码

#include<bits/stdc++.h>
#define N 210
#define M 20
using namespace std;

char s[N], c[5] = {'K', 'W', 'I', 'N', 'G'};
int a[N];
bool f[N][N][M], g[N][N][M];

int modify(char x)
{
    if(x == 'W') return 1;
    if(x == 'I') return 2;
    if(x == 'N') return 3;
    if(x == 'G') return 4;
}

int main()
{
    for(int i = 1; i <= 4; i ++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= 4; i ++)
        for(int j = 1; j <= a[i]; j ++)
        {
            scanf("%s", s);
            g[i][modify(s[0])][modify(s[1])] = true;
        }
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for(int i = 1; i <= n; i ++)
        f[i][i][modify(s[i])] = true;
    for(int l = 1; l <= n; l ++)
        for(int i = 1; i <= n - l + 1; i ++)
        {
            int j = l + i - 1;
            for(int k = i; k < j; k ++)
                for(int a = 1; a <= 4; a ++)
                    for(int b = 1; b <= 4; b ++)
                        for(int c = 1; c <= 4; c ++)
                            if(g[a][b][c] && f[i][k][b] && f[k + 1][j][c])
                               f[i][j][a] = true;
        }
    bool flag = false;
    for(int i = 1; i <= 4; i ++)
        if(f[1][n][i]) printf("%c", c[i]), flag = true;
    if(!flag) printf("The name is wrong!");
    return 0;
} 

心得

有时候逆向思考问题会得到不错的想法啊。