自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 22:20:19，当前版本为作者最后更新于2020-04-14 15:48:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P6388

题意简述：

将一个字符串分成三段，把每一段倒过来拼成一个新字符串，求字典序最小的一个新字符串

字符串长度 $3 \leq n \leq 50$

---

这题十分玄学，有两种正解

为了便于分析，设分成的段数为$k$

---

分段做法 ：

搜索枚举每一次分段的分段位置，找出结果最小的一个

所有分段可能数目大体相当于在$n$个物品里选$k-1$个物品方案数目

大概=$n^{k-1}$，处理结果时$O(n)$，所以综合复杂度$O(n^k)$，

---

DP做法

我们知道，DP就是记忆化搜索，也就是改进的爆搜

设$f[i][j]$为从$i$开始到结尾，一共用j次分段的最小字典序

我们枚举这一段结尾的字符位置$l$

则$f[i][j]=min(f[i][j],u+f[l+1][j-1])(i \leq l \leq n-1-j)$

其中$u$是自$i$到$l$的回文

枚举$i,j,l$为$O(kn^2)$，而处理u为$O(n)$

综合复杂度为$O(kn^3)$

---

现在，来到这道题精髓的地方，将$k=3$带回原式。

DP做法复杂度=$O(3*n^3)$，约$O(n^3)$

看上去很烂的分段是$O(n^3)$

也就是说，看上去烂的算法在这道题里跑的挺快！

经过实际测试，DP做法是一共20ms，而分段算法是19ms！快了1ms！所以这题很玄学

---

注意事项：

截取原来的字符串可以使用string的substr函数，这个函数用法是

a.substr(开始位置,截取字符数);

反转字符串可以用algorithm的reverse函数，这个函数用法是

reverse(a.begin(),a.end());

---

现在把两种AC代码全部放上

DP做法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

string f[100][5];
string a;
string u;
int main(){
	cin>>a;
	int n=a.size();
	int k=3;
	for(int i=n-1;i!=-1;i--){
		u=a.substr(i,n-i);
		reverse(u.begin(),u.end());
		f[i][0]=u; 
		for(int j=1;j<k;j++){ 
			f[i][j]="|";
			for(int l=i;l<=n-1-j;l++){ 
				string u=a.substr(i,l-i+1);
				reverse(u.begin(),u.end());
				f[i][j]=min(f[i][j],u+f[1+l][j-1]);
			}
		}
	}
	cout<<f[0][k-1];
}

分段算法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

string mi,a;
int n,k;
int f[1000];


void ch(){
	string a1,a2;
	a2.clear();
	int p=0;
	for(int i=1;i<=k;i++){
		a1=a.substr(p,f[i]-p);
		reverse(a1.begin(),a1.end());
		a2=a2+a1;
		p=f[i];
	}
	mi=min(mi,a2);
}

int sou(int m,int c){
	if(c==3){
		ch();return 0;
	}
	for(int i=m;i<=n-k+c;i++){
		f[c]=i;
		sou(i+1,c+1);
	}
	return 0;
}

int main(){
	mi="|";
	cin>>a;
	n=a.size();
	k=3;
	f[k]=n;
	sou(1,1);
	cout<<mi;
	return 0;
}

---

感谢大家观赏！

希望不要抄袭