自动搬运

查看原文

来自洛谷，原作者为

	天南地北 生活的船舵掌握在自己手中，明天或者意外谁会先来，不如谈谈今日，又做了些什么

搬运于2025-08-24 22:23:12，当前版本为作者最后更新于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]);
  }
}