【区间dp、字符串处理】P4290 [HAOI2008] 玩具取名 题解

前言

毒瘤的字符串杂题

题意

给定 $A,B,C,D(A,B,C,D\le 16)$ 四个数，依次代表 W I N G 四个字母分别能用哪些含有 W I N G 四个字母且长度为 $2$ 的字符串表示，如以下输入样例：

1 1 1 1
II
WW
WW
IG
IIII

代表：
每一个 W 可替换为 II，每一个 I 和 N 可以替换为 WW，每一个 G 都可以替换为 IG。最后给定一个字符串 $L$，问 WING 中哪些字母能够通过多次以上的替换变为所求的字符串（长度 $n$ 小于 $200$），若无则 输出 The name is wrong!

如样例中 IIII->WW->I 和 IIII->WW->N 故输出 IN。

思路

显而易见区间dp（tag就是区间dp，问题是如何转移）。

首先对于每一个 $ABCD$ 写一个对应的输入。开一个 map $P$表示一个长度为 $2$ 的字符串可以由那些字母变过来，代码如下：

// 主函数外面
map<string,string>P;
void input(int x,string y) {string S;for(int i = 1;i <= x;i++) {cin >> S;P[S] += y;}
}// 主函数输入
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
input(a,"W"),input(b,"I"),input(c,"N"),input(d,"G");

记 $d{p}_{i,j}$ 表示区间 $i$ 到 $j$ 可由那些字母变来，则 $d{p}_{i,i}=L_i$

对于每一个长度不小于 $2$ 的串，可由以下变来：

$d{p}_{i,k},d{p}_{k+1,j}$ ，代表字符串分为 $[i,k]$ 和 $[k+1,j]$ 两个部分。则如果 $dp[i,k]=I,dp[k+1,j]=I$，则 $d{p}_{i,j}$ 中必有 $p_{II}$ 这一项：

bool w_1,i_1,n_1,g_1;
void check(string p,string q) {int p1 = p.size(),q1 = q.size();for(int i = 0;i < p1;i++) {for(int j = 0;j < q1;j++) {string new_str = p.substr(i,1) + q.substr(j,1);new_str = P[new_str];if(new_str.find("W") <= new_str.size()) w_1 = true;if(new_str.find("I") <= new_str.size()) i_1 = true;if(new_str.find("N") <= new_str.size()) n_1 = true;if(new_str.find("G") <= new_str.size()) g_1 = true;}}
} 

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c,d;
map<string,string>P;
void input(int x,string y) {string S;for(int i = 1;i <= x;i++) {cin >> S;P[S] += y;}
}
string L;
int n;
string dp[205][205];
bool w_1,i_1,n_1,g_1;
void check(string p,string q) {int p1 = p.size(),q1 = q.size();for(int i = 0;i < p1;i++) {for(int j = 0;j < q1;j++) {string new_str = p.substr(i,1) + q.substr(j,1);new_str = P[new_str];if(new_str.find("W") <= new_str.size()) w_1 = true;if(new_str.find("I") <= new_str.size()) i_1 = true;if(new_str.find("N") <= new_str.size()) n_1 = true;if(new_str.find("G") <= new_str.size()) g_1 = true;}}
} 
signed main() {scanf("%lld %lld %lld %lld",&a,&b,&c,&d);input(a,"W"),input(b,"I"),input(c,"N"),input(d,"G");cin >> L,n = L.size();L = " " + L;for(int i = 1;i <= n;i++) dp[i][i] = L[i];for(int i = 2;i <= n;i++) {for(int l = 1;l + i - 1 <= n;l++) {int r = l + i - 1;w_1 = false,i_1 = false,n_1 = false,g_1 = false; for(int k = l;k < r;k++) {if(dp[l][k] == "The name is wrong!" or dp[k + 1][r] == "The name is wrong!") continue;check(dp[l][k],dp[k + 1][r]); if(w_1 and i_1 and n_1 and g_1) break;}if(!(w_1 or i_1 or n_1 or g_1)) dp[l][r] = "The name is wrong!";if(w_1) dp[l][r] += "W";if(i_1) dp[l][r] += "I";if(n_1) dp[l][r] += "N";if(g_1) dp[l][r] += "G";}}cout<<dp[1][n];return 0;
}