自动搬运

查看原文

来自洛谷，原作者为

	kradcigam 永不放弃之心，将成为贯穿逆境之光！

搬运于2025-08-24 21:23:15，当前版本为作者最后更新于2019-11-16 15:05:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

首先，看到这道题目，我首先想到的是暴搜，通过$vector$来搞，代码也是很短的。

这里用了一个类似于分治的思想

把一个大问题转化为小问题

先枚举第一个单词，之后把能拼接在它后面的单词都一个一个的去试，哪个最优选哪个

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	T f=1;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	x*=f;
}//快读，常数优化
template<typename T>inline void write(T x){
	if(x<0){
		putchar('-');
		write(x*-1);
		return;
	}
	if(x>9)write(x/10);
	putchar(x%10+48);
}//快写，常数优化
string st[18];
vector<int>v[210];//动态数组
int f[18];//标记数组
int dfs(int x){
	int ans=0;
	for(auto i:v[st[x][st[x].size()-1]])//v数组是存第1个字母的一个容器
		if(!f[i]){
			f[i]=1;//标记这个字符串已经用过了
			ans=max(ans,dfs(i));//打擂
			f[i]=0;//回溯
		}
	return ans+st[x].size();
}
int main(){
	int ans=0,n;
	read(n);//读入
	for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);//读入，放入vector容器
	for(int i=1;i<=n;i++){
		f[i]=1;//表记
		ans=max(ans,dfs(i));//打擂法找到最优解
		f[i]=0;//回溯
	}
	write(ans);//输出
    return 0;
}

然后，你会发现你只得了70分，开$O(2)$试试？TLEagain!

想一想更优秀的算法，加记忆化？是的！

正文

储存状态

如何存状态

我们发现每一个字符串的状态都要么是0，要么是1，所以我们可以用二进制的思想去压缩状态。

开数组很充裕，浪费也不要紧。

判断状态

如何去判断第$i$个单词有没有用过

从右往左这个数二进制的第$i$位是$1$，就代表这个单词用过，反之$0$就代表这个单词没用过。

但给你这么一个数，你该这么去判断呢？

用位运算！

如果第$i$为是$1$，那么$x>>(i-1)$后$\mod2$就是$1$

如果第$i$为是$0$，那么$x>>(i-1)$后$\mod2$就是$0$

那么判断这个单词是否用过，我们就可以这么写

if(!((y>>(i-1)&1))//按位与，只有两个数这一位都是1才为1，所以只有当最后一位是1，这个数才会是1，否则是0

标记状态

如何将这一位变成$1$

将这一位变成$1$，我们可以用位运算中的按位或——两位都是$0$，这一位的得数才为$0$

y|(1<<(i-1))

这应该是很显然的

总结

现在就可以看总的代码了

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
	T f=1;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	x*=f;
}
template<typename T>inline void write(T x){
	if(x<0){
		putchar('-');
		write(x*-1);
		return;
	}
	if(x>9)write(x/10);
	putchar(x%10+48);
}
string st[18];
vector<int>v[210];
int f[17][1<<17];
int dfs(int x,int y){
	if(f[x][y])return f[x][y];
	int ans=0;
	for(auto i:v[st[x][st[x].size()-1]])
		if(!((y>>(i-1))&1))ans=max(ans,dfs(i,y|(1<<(i-1))));
	return f[x][y]=ans+st[x].size();
}
int main(){
	int ans=0,n;
	read(n);
	for(int i=1;i<=n;i++)cin>>st[i],v[st[i][0]].push_back(i);
	for(int i=1;i<=n;i++)ans=max(ans,dfs(i,(1<<(i-1))));
	write(ans);
    return 0;
}

刚开始我认为这应该没有多少重复运算，所以我写了个暴搜，但是，我写了记忆化之后惊奇地发现，暴搜总用时$4.00s$,也就是$4000ms$，而记忆化搜索总用时$73ms$，快了不只一点。但是空间确实消耗很大。

编程中有很多算法，用空间换时间，记忆化搜索就是这么一个代表，我们要学习这种思想，想出更巧妙的办法！