自动搬运

查看原文

来自洛谷，原作者为

	hewo NOIP 2021 rp++

搬运于2025-08-24 21:39:18，当前版本为作者最后更新于2021-10-15 16:15:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题题目、样例有误。

正确的题面：

洛谷P6701

LOJ (数据水一点)

使用区间DP+状压：

转化为将给定的字符串能压缩成的只含有 S 的最短字符串。

对于给定的分裂（合并）规则，也就是两个字符合并为一个字符，我们用状压思想，以二进制来存储这两种字符可以合并为那些种类的字符，也就是:

c[get(ins[1])][get(ins[2])]|=(1<<(get(ins[0])));

再考虑如何DP。

设 $dp_{i,j}$ 表示区间 $[i,j]$ 中的答案，$git_{i,j}$ 表示区间 $[i,j]$ 可以合并成为那些字符。

在进行区间DP的同时，更新 $git_{i,j}$，如果合并出了 S，则 $dp_{i,j}=1$。

我们还可以进行一些优化：

1. 开小数组。
2. 很多大佬采用的是枚举每个字符，其实可以直接存每一种合并，再来枚举，这样会快一些。

具体看代码吧，还是比较好理解的。

#include<bits/stdc++.h>

using namespace std;

const int MX=105;
#define LL long long
#define inf 0x3f3f3f3f

#define modn 10000

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int m;//规则数

char ins[10];
int c[30][30];//合并用

int git[MX][MX];

char s[MX];
int n;

inline int get(char x)
{
	return x-'A'+1;//1~26
}

int dp[MX][MX];

inline void csh()
{
	memset(dp,0x3f,sizeof(dp));
	memset(git,0,sizeof(git));
}

struct tCod
{
	int x,y;
}cod[800];
int idx=0;

int main(int argc, char const *argv[])
{
	m=read();
	for(int i=1;i<=m;i++)
	{
		scanf("%s",ins);
		if(c[get(ins[1])][get(ins[2])]==0)
		{
			cod[++idx]=tCod{get(ins[1]),get(ins[2])};
		}
		c[get(ins[1])][get(ins[2])]|=(1<<(get(ins[0])));

	}
	int T;
	T=read();
	while(T--)
	{
		csh();
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='S')
			{
				dp[i][i]=1;
			}
			git[i][i]|=(1<<(get(s[i])));
		}
		for(int len=0;len<n;len++)
		{
			for(int l=1;l+len<=n;l++)
			{
				int r=l+len;
				//l~k k+1~r
				for(int k=l;k<=r-1;k++)
				{
					dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
					for(int q=1;q<=idx;q++)
					{
						int x=cod[q].x,y=cod[q].y;
						if(c[x][y])//如果这两个字符能合并
						{
							//git是放单字符的多情况的，如果能合并的话就合并，一个区间合并成一个字符，然后记录这一个字符有多少种情况
							if((git[l][k]&(1<<(x)))&&((git[k+1][r])&(1<<(y))))
							{
								git[l][r]|=c[x][y];
								//printf("%d %d %d %d\n",l,k,r,c[x][y]);
							}
						}
					}	
					if((git[l][r]&(1<<(get('S')))))
					{
						dp[l][r]=1;//如果合并出S了，就直接变成1
					}
				}
			}
		}
		if(dp[1][n]==inf) printf("NIE\n");
		else printf("%d\n",dp[1][n]);
	}
	return 0;
}