题解 P6701 【[POI1997] Genotype】

天南地北 · 2020-11-18 14:08:11 · 题解

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

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

其实这个问题就像十分朴素的区间DP，考虑有一个dp[l][r]，我们需要枚举一个中点k，计算求它所需要的特定的串的个数dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);

当然了，这个特定的串只包含大写字母S，其实我们可以通过状态压缩的方式，表示当前区间可以变成的字符有哪些，那么就是要考虑分成的两个部分可以变成的字符以及可以组合成的字符

最后只要dp[1][stlen]只要不是极大值，就是有解，解是dp[1][stlen]，否则无解。

参考程序

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=300+10;
int n,k;
int Merge[maxn][maxn],zt[maxn][maxn],dp[maxn][maxn];
int main()
{
  scanf("%d",&n);
  rep(i,1,n)
  {
    string ch;
    cin>>ch;
    Merge[ch[1]-'A'+1][ch[2]-'A'+1]|=1<<(ch[0]-'A'+1);
  }
  scanf("%d",&k);
  while(k--)
  {
    memset(zt,0,sizeof(zt));
    memset(dp,0x3f,sizeof(dp));
    string now;
    cin>>now;
    int stlen=now.size();
    rep(i,0,stlen-1)
    {
      if(now[i]=='S') dp[i+1][i+1]=1;
      zt[i+1][i+1]|=(1<<(now[i]-'A'+1));
    }
    rep(len,0,stlen-1)
    {
      for(int l=1;l+len<=stlen;l++)
      {
        int r=l+len;
        rep(k,l,r-1)
        {
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            rep(x,1,26)
                rep(y,1,26)
                    if((zt[l][k]&(1<<(x)))&&(zt[k+1][r]&(1<<(y))))
                        zt[l][r]|=Merge[x][y];
        }
        if(zt[l][r]&(1<<('S'-'A'+1))) dp[l][r]=1;
      }
    }
    if(dp[1][stlen]>=0x3f3f3f3f) printf("NIE\n");
    else printf("%d\n",dp[1][stlen]);
  }
}