自动搬运

查看原文

来自洛谷，原作者为

	JoaoFelix c1c

搬运于2025-08-24 21:38:26，当前版本为作者最后更新于2020-09-24 11:47:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

又来一道玄学题orz

我们发现这题的状态数应该不会太多，我们只要能找到合适的压缩状态的办法，就能过题。

因为这个cnt只到3的范围左右，于是我们考虑dp，如果我们能压出的是dp的数组？并且这个里面的dp值不会很大，3左右的最多。

于是我们开始考虑怎么dp，记录当前匹配到第i个串的第j位的个数有多少？我们只需要维护这个dp值就可以。

这个非常好转移，如果填完了，就把所有新开始的位置加上填完的总数组解，反之我们就是向前一位转移。

于是我们考虑如果有某一个字符串填完，把这个填完的总数相加，如果大于3就直接找到答案了，反之我们就继续bfs。

这里具体的实现我们用一个vector来压一个dp数组，这个dp数组我们把i个串的都拼在一起，搞一个一位数组存在vector里面就好。

然后我们用一个map来映射一下这个vector，转移就是枚举‘0’~‘1’然后不断bfs，大致是这样的一个思路。

具体复杂度我也不会证，但是跑的飞快，就O(能过)

代码：

#include<bits/stdc++.h>
#define LL long long
#define vi vector<int>
using namespace std;
int n,id[35][55],totl,dfn;
string str[35];
vi s,t;map<vi,int>mp;
queue<vi>q;
int main(){
	scanf("%d",&n);
	for(int i=1,l;i<=n;i++){
		cin>>str[i];l=str[i].size();totl+=l;
		if(!l){puts("0");return 0;}
		for(int j=0;j<l;j++)id[i][j]=dfn++;
	}
	s.resize(totl);t.resize(totl);
	for(int i=1;i<=n;i++)s[id[i][0]]=1;
	mp[s]=0;q.push(s);
	while(!q.empty()){
		vi u=q.front();q.pop();int ns=mp[u];
		for(char ch='0';ch<='1';ch++){
			for(int i=0;i<totl;i++)t[i]=0;
			int ed=0;
			for(int i=1,l;i<=n;i++){
				l=str[i].size();
				for(int j=0;j<l;j++)if(str[i][j]==ch){
					if(j==l-1)ed+=u[id[i][j]];else t[id[i][j+1]]=u[id[i][j]];
				}
			}
			if(ed>=3){printf("%d\n",ns+1);return 0;}
			for(int i=1;i<=n;i++)t[id[i][0]]=ed;
			if(!mp.count(t))mp[t]=ns+1,q.push(t);
		}
	}
	puts("-1");
	return 0;
}