P4290 玩具取名题解

· · 题解

介绍一下这个题我自己的思路。

一、暴力

看完这个题，第一感觉就是把所有WING字母可以变形的形式枚举出来，然后直到目标序列出来或者枚举完全部的变形形式（结束条件是目前枚举的序列长度比目标序列长度大的时候）。那么可以用bfs做。经计算，如果每个字母只变成一种双字符的时候，每一层枚举长度大约为 \frac{i(i+1)}{2} 种（i为第i层）那么总共需要枚举:

\sum_{i=1}^{n}\frac{i(i+1)}{2}

那么时间复杂程度大约为O(n^3)，但是这个只是每个字母变成一种序列，如果每个字母变成m个序列的话大约为O(mn^3)，优化的话应该还是可以得到几分的。（多少分我就不知道了，有兴趣的可以自己打一遍试试）

二、动态规划

再重新看这一道题，如果按着上面暴力解法反着想的话，那么久可以把这一道题理解为：给你一个字母序，按规定可以将特定的两个连续字母合并成一个字母，问最后可以合并成哪一个单字母。

这里想后，我第一感觉就是可能类似于石子合并的题了。于是我便用区间dp试做了一下。

首先，区间dp先定义dp[l][r]，即再区间[l,r]的dp值(l，r可能可以滚动数组）。但是这一题单只有l，r是不够的，因为每一个字母都可能会合并成区间[l，r]，那么就可以添加一维，dp[l][r]['c']，即在区间[l，r]中是否可以合并成c这一个字母。

那么可以得出状态转移方程：

dp[i][j]['c']=dp[i][k]['cl'] & dp[k+1][j]['cr']

其中[i，k]与[k+1，j]为[i，j]的子集，[i，k]∪[k+1，j]=[i,j]（废话），‘cl’与‘cr’分别为字符‘c’可以变成的某一个双字符的左右字符。

数组的初始化为：

dp[i][i][s[i]]=1

其中s[i]为读入字符串的第i个字符。（即自己可以变成自己）

这个状态方程的意思就是如果在[i，k],[k+1，j]区间中可以分别转化为cl与cr的话，那么[i，j]就可以由c转化成，其中k可以在[i,j]中枚举。

举个例子，如样例中，初始化为dp[1~4][1~4]['I']=1,在区间i=1,j=2中，dp[1][2]['W']=dp[1][1]['I']=1,同理，在区间dp[3][4]['W']=1,那么i=1,j=4的中，dp[1][4]['N']=dp[1][2]['W']&dp[3][4]['W']=1，因此N为可行解。

算法维护：

  1. 由于字母转化成数组维度有点麻烦（可以用map或者直接用字母的ASCII来当数组下标）每个字母可以分别映射的数字，即字符W,I,N,G可以分别对应1,2,3,4

  2. 每个字符变形的双字符可以用邻接表储存

  3. 另外要强调，在读入字符时，要小心读入到' ' '\n'（即空格与回车换行）

代码（未剪枝50分）：

//n为字符串长度
for(int i=0;i<n;i++)
    for(int j=i-1;j>=0;j--)//枚举区间
            for(int g=1;g<=4;g++)//枚举字母
            {
            //****标记点****
                for(int m=head[g];m;m=que[m].nx)
                {
                        l=que[m].a;r=que[m].b;//a,b分别为左字母右字母
                        for(int k=j;k<i;k++)//枚举子集
                        dp[j][i][g]|=(dp[j][k][l]&dp[k+1][i][r]);
                }
            }

tips：由于我写的是j>i,所以是区间[j，i]，如果觉得难看可以让i从n-1枚举到0，j=i+1,j<n，那么就是i>j，是区间[i,j]了;

很明显时间复杂大约也为O(mn^3)，还是可能会超时的，但比起暴力枚举好了很多。我们可以进行剪枝，如果g已经可以变成区间[i][j]字符串了，那么针对g就不用继续枚举这个区间了。

即在本代码标记点处加入 if(dp[j][i][g]) continue;

AC总代码（仅供参考）：

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pc(a) putchar(a)
#define rg register
const ll maxn=1100;
void gc(char &a)
{
    a=getchar();
    while(a==' '||a=='\n') a=getchar();
}
ll read(){
    char c;ll x=0;bool flag=0;gc(c);
    while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),c=getchar();}
    return flag?-x:x;
}
void pr(ll x){
    if(x<0){x=-x;pc('-');}
    if(x>9) pr(x/10);
    pc(x%10+48);
}
//----快读区域-----
struct edge
{
    char a,b;
    ll nx;
    edge(char a,char b,ll nx):a(a),b(b),nx(nx){}
    edge(){}
}que[80000];//邻接表
ll head[5],en;
map<char,ll> p;//用来更改WING的值
void edgepush(int i,char a,char b)//建边
{
    que[++en]=edge(p[a],p[b],head[i]);
    head[i]=en;
}
bool dp[maxn][maxn][5];//精髓
ll n,a[5],l,r;
string s;//读入字符
char u,v;
bool flag;//用来判断是否有字符输出
int main()
{
    p['W']=1;p['I']=2;p['N']=3;p['G']=4;
    for(int i=1;i<=4;i++)
    a[i]=read();
    for(int i=1;i<=4;i++)
    for(int j=1;j<=a[i];j++)
    {
        gc(u);gc(v);
        edgepush(i,u,v);
    }
    cin>>s;n=s.size();
    for(int i=0;i<n;i++)
    dp[i][i][p[s[i]]]=1;
    for(int i=0;i<n;i++)
    for(int j=i-1;j>=0;j--)
    for(int g=1;g<=4;g++)
    {
        if(dp[j][i][g]) continue;
        for(int m=head[g];m;m=que[m].nx)
        {
            l=que[m].a;r=que[m].b;
            for(int k=j;k<i&&!dp[j][i][g];k++)
            dp[j][i][g]|=(dp[j][k][l]&dp[k+1][i][r]);
        }
    }
    if(dp[0][n-1][1]){pc('W');flag=1;}
    if(dp[0][n-1][2]){pc('I');flag=1;}
    if(dp[0][n-1][3]){pc('N');flag=1;}
    if(dp[0][n-1][4]){pc('G');flag=1;}
    if(!flag) puts("The name is wrong!");
    return 0;
}