题目描述
其实题意还是不太好理解的
给定一个字符串,并给定一些扩充方式,求该字符串可以由哪几个单独的字符扩充得到
需要注意到的是,最初的一个字符必须是 “WING” 中的一个
而且扩充得到的两个新字符也一定是 “WING” 中的一个 (这两条是原题规定好的)
其实给的总串中可以有 “WING” 外的字符,但似乎数据没有注意这个,就算有也只需特判一下输出无解即可
解题思路
题目中只有4种字符,直接用1~4的数字来代替四个字符会更方便
可以看到标签是区间DP,直接考虑设计状态(话说只有我这种蒟蒻会看标签偷思路
$f[l][r][c]$表示将从 l 到 r 的子串缩成字符 c 是否可行 (c是1~4
接下来考虑状态计算,首先先初始化区间长度为1的状态
对于每个状态,从状态的实际意义考虑,我们要将 l~r 的区间合并为一个字符c
那么最后一次合并一定是先将总串合并成两个字符 a 和 b ,这两个字符再合并成c
我们枚举 a 和 b ,也就是枚举字符 c 能扩充到哪两个字符
然后再枚举 a 和 b 所对应两部分的分界点 k ,最终得到转移式:
f[l][r][c] = ( f[l][k][a] && f[k+1][r][b] )
时间复杂度
总共有 $n \times n \times 4$ 个状态,求每一个状态需要 $路径数 \times 区间长度$ 次计算
那么一共是:$200 \times 200 \times 4 \times 16 \times 200$ 大约是 $5 \times 10^8$
但最后一个200跑不满,所以很轻松过掉了,本人代码最后一个点跑了不到0.4秒
AC代码
//码风若不习惯,还请见谅
#include <bits/stdc++.h>
using namespace std;
int n[5],m,way[5][20][2],a[210];
bool f[210][210][5];
int p(char c)
{
if(c=='W') return 1;
if(c=='I') return 2;
if(c=='N') return 3;
if(c=='G') return 4;
}
int main()
{
scanf("%d %d %d %d",&n[1],&n[2],&n[3],&n[4]);
for(int i=1;i<=4;i++)
for(int j=1;j<=n[i];j++)
{
string w;
cin>>w;
way[i][j][0]=p(w[0]);
way[i][j][1]=p(w[1]);
}
string s;
cin>>s;
m=s.length();
for(int i=0;i<m;i++)
{
a[i+1]=p(s[i]);
f[i+1][i+1][a[i+1]]=true;
}
for(int len=2;len<=m;len++)
for(int i=1;i+len-1<=m;i++)
{
int l=i,r=i+len-1;
for(int c=1;c<=4;c++)
for(int k=1;k<=n[c];k++)
{
int a=way[c][k][0],b=way[c][k][1];
for(int t=l;t<r;t++) f[l][r][c]|=(f[l][t][a]&&f[t+1][r][b]);
}
}
if(f[1][m][1]) printf("W");
if(f[1][m][2]) printf("I");
if(f[1][m][3]) printf("N");
if(f[1][m][4]) printf("G");
if(!f[1][m][1]&&!f[1][m][2]&&!f[1][m][3]&&!f[1][m][4]) printf("The name is wrong!");
return 0;
}
2022年2月28日15:35:07