[POI1997] Genotype

题目背景

Genotype 是一个独特的基因串。a

题目描述

我们可以用大写英文字母 $A-Z$ 来描述 Genotype，每个字母就代表一个基因。

规定一种「分裂」规则，由三个大写字母 $A_1{A}_2{A}_3$ 组成，代表 $A_1$ 可以「分裂」为 $A_2{A}_3$。

现在给定 $n$ 个「分裂」规则和 $k$ 个 Genotype，判断这些 Genotype 是否能从一个特定的 只包含大写字母 $S$ 的 串通过「分裂」规则得到，如果可以的话输出特定的串的长度的最小值，如果不可以的话输出 NIE。

输入格式

第一行一个整数 $n$ 代表「分裂」规则数。
接下来 $n$ 行每行三个大写字母 $A_1,A_2,A_3$ 代表一个「分裂」规则。
接下来一行一个整数 $k$ 代表给定的 Genotype 数。
接下来 $k$ 行每行若干个大写字母表示一个 Genotype。

输出格式

$k$ 行：

• 如果没有特定的串通过「分裂」规则得到这个 Genotype，输出 NIE。
• 如果有特定的串通过「分裂」规则得到这个 Genotype，输出这个特定的串的最小长度。

样例 #1

样例输入 #1

6 SAB SBC SAA ACA BCC CBC 3 ABBCAAABCA CCC BA 

样例输出 #1

3 1 NIE 

提示

数据规模与约定

对于 $100\%$ 的数据，$1\le n,k\le 2000$，Genotype 的长度最大为 $100$。

大意：判断一个字符串是否能够通过一个特定的串分裂得到，如果可以的话输出特定的串的长度的最小值，如果不可以的话输出NIE。

俗话说得好，正难则反，分裂很难，但是我们可以想：我们可不可以将给定的字符串进行合并得到这个最小特定的串呢？

于是我们可以定义一个三维的区间dp[$i$][$j$][$s$]表示区间$i$-$j$能否合成为字符s然后依次去枚举左端点和区间长度，再在这个枚举到的这个区间里枚举中间点k并更新该区间能合成的字符！

那最后的答案存在哪呢？大多数人第一反应是dp[$l$][$r$][$19$]，实则不然，因为字符串可能是由多个$S$分裂而成，所以我们还需定义一个dp2[$i$]表示前i个字符所需最少$S$数量

最后答案即是dp2[$n$]
$n$为字符串长度

代码如下：

#include<bits/stdc++.h> using namespace std; const int MAXN = 1e2 + 5; int n , k , dp[MAXN][MAXN][27] , a[2005][27] , dp2[MAXN];//dp状态已解释，不过多赘述  char a2 , b , c , s[MAXN]; int main() { 
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);//玄学优化  cin >> n; for (int i = 1 ; i <= n ; i ++) { 
    cin >> a2 >> b >> c; a[i][0] = a2 - 'A' + 1; a[i][1] = b - 'A' + 1; a[i][2] = c - 'A' + 1;//用a数组保存b字符与c字符可合成a字符  } cin >> k;//样例组数  while(k --) { 
    cin >> s + 1; int m = strlen(s + 1); for (int i = 1 ; i <= m ; i ++) dp2[i] = 0x3f3f3f3f;//用来比最小值  for (int i = 1 ; i <= m ; i ++) { 
    for (int j = i ; j <= m ; j ++) { 
    for (int k = 1 ; k <= 26 ; k ++) { 
    dp[i][j][k] = 0;//初始化  } } } dp[0][0][19] = 1;//初始化，无过多实际意义  for (int i = 1 ; i <= m ; i ++) { 
    dp[i][i][s[i] - 'A' + 1] = 1;//自己合成自己肯定可以  } for (int i = 2 ; i <= m ; i ++) { 
   //枚举区间长度  for (int j = 1 ; j <= m - i + 1 ; j ++) { 
   //枚举左端点  int p = j + i - 1;//右端点  for (int q = j ; q < p ; q ++) { 
   //枚举中间点  for (int x = 1 ; x <= n ; x ++) { 
   //一共有x种合成方式  if (dp[j][q][a[x][1]] && dp[q + 1][p][a[x][2]]) { 
   //若左区间可以合成a[x][1]，右区间可以合成啊a[x][2]，那么j-p就可以合成a[x][0]  dp[j][p][a[x][0]] = 1; } } } } } for (int i = 1 ; i <= m ; i ++) { 
    for (int j = 0 ; j < i ; j ++) { 
    if (dp[j + 1][i][19]) { 
   //j+1到i可以合成字符S  dp2[i] = min(dp2[i] , dp2[j] + 1);// 那么1到j最小的S数量加上j+1到i的这个S便是一组解，与原答案比min  } } } if (dp2[m] == 0x3f3f3f3f) puts("NIE");//若没有更新1到m的值，即无解  else printf("%d\n", dp2[m]);//否则输出  } return 0; } 

姊妹题

[HAOI2008] 玩具取名

题目描述

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

样例输出 #1

IN 

提示

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

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

该题是基因串的弱化版，绿题和蓝题的区别

但本人最开始没读懂题，以为样例中是由$I$$N$分裂过来的，但实际上是$I$、$N$都可以作为答案，就这样卡了很久

题读懂后，这道题瞬间简单起来，不愧是绿题，我们只需把基因串的代码稍稍改动一下即可，详情如下：

• 更改输入方式，利用$t$$o$$t$累计变换方式
• 最后输出时一一判断1到$n$能否合成$W、I、N、G$，不能则输出The name is wrong!

代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 2e2 + 5; int n, k, dp[MAXN][MAXN][27], a[2005][4] , W , I , N , G , tot; char b, c, s[MAXN]; int main() { 
    ios::sync_with_stdio(false); cin >> W >> I >> N >> G; for (int i = 1 ; i <= W ; i++) { 
    cin >> b >> c; a[++ tot][0] = 'W' - 'A' + 1; a[tot][1] = b - 'A' + 1; a[tot][2] = c - 'A' + 1; } for (int i = 1 ; i <= I ; i++) { 
    cin >> b >> c; a[++ tot][0] = 'I' - 'A' + 1; a[tot][1] = b - 'A' + 1; a[tot][2] = c - 'A' + 1; } for (int i = 1 ; i <= N ; i++) { 
    cin >> b >> c; a[++ tot][0] = 'N' - 'A' + 1; a[tot][1] = b - 'A' + 1; a[tot][2] = c - 'A' + 1; } for (int i = 1 ; i <= G ; i++) { 
    cin >> b >> c; a[++ tot][0] = 'G' - 'A' + 1; a[tot][1] = b - 'A' + 1; a[tot][2] = c - 'A' + 1; } cin >> s + 1; int m = strlen(s + 1); dp[0][0]['W' - 'A' + 1] = 1; dp[0][0]['I' - 'A' + 1] = 1; dp[0][0]['N' - 'A' + 1] = 1; dp[0][0]['G' - 'A' + 1] = 1; for (int i = 1; i <= m; i++) { 
    dp[i][i][s[i] - 'A' + 1] = 1; } for (int i = 2; i <= m; i++) { 
    for (int j = 1; j <= m - i + 1; j++) { 
    int p = j + i - 1; for (int q = j ; q < p ; q ++) { 
    for (int x = 1 ; x <= tot ; x ++) { 
    if (dp[j][q][a[x][1]] && dp[q + 1][p][a[x][2]]) { 
    dp[j][p][a[x][0]] = 1; } } } } } bool f = 0; if (dp[1][m]['W' - 'A' + 1]) { 
    printf("W"); f = 1; } if (dp[1][m]['I' - 'A' + 1]) { 
    printf("I"); f = 1; } if (dp[1][m]['N' - 'A' + 1]) { 
    printf("N"); f = 1; } if (dp[1][m]['G' - 'A' + 1]) { 
    printf("G"); f = 1; } if (!f) printf("The name is wrong!"); return 0; } 

代码相似度实在太高，注释都懒得写了