自动搬运

查看原文

来自洛谷，原作者为

	xiazha **

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

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

以下是正文

非常厉害的题目，观察到 $n\le10$，爆搜，但是复杂度是 $O(n!n^3)$ 的，显然超时，想到加剪枝，这里需要挖掘性质：

注意到设一次操作前的数列为 $a$，操作后为 $b$，那么若 $\sum_{i=1}^{n-1} [a_i+1=a_{i+1}]\ge \sum_{i=1}^{n-1} [b_i+1=b_{i+1}]$，那么这次操作是无效的，不继续搜索，这样就能过了，如果你想要更快，那么观察到答案 $\le 6$，可以进一步节省时间。

注：才发现是最优解

map<long long,int> mp,pm;
long long val()
{
	long long v=0;
	for(int i=1;i<=n;i++) v+=(a[i]-1)*pw[i];
	return v;
}
void dfs(int step)
{
	long long v=val();
	if(mp[v]<=step&&pm[v]) return;
	if(step>=6||step>=minn) return;
	mp[v]=step;pm[v]=1;
	if(v==ans) minn=min(minn,step);
	int ppp=0,ppp1=0;
	for(int p=1;p<n;p++)
		if(a[p]+1==a[p+1])
			ppp++;
	for(int p=1;p<n;p++)
		if(a[p]>a[p+1])
			ppp1++;
	for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++)
			for(int k=j;k<=n;k++)
			{
				int cnt=0,b[11];
				memcpy(b,a,sizeof(a));
				for(int p=j+1;p<=k;p++) a[++cnt]=b[p];
				for(int p=1;p<=i;p++) a[++cnt]=b[p];
				for(int p=k+1;p<=n;p++) a[++cnt]=b[p];
				for(int p=i+1;p<=j;p++) a[++cnt]=b[p];
				int pp=0,pp1=0;
				for(int p=1;p<n;p++)
					if(a[p]+1==a[p+1]) pp++;
				for(int p=1;p<n;p++)
					if(a[p]>a[p+1]) pp1++;
				if(ppp>=pp||pp1>ppp1)
				{
					memcpy(a,b,sizeof(b));
					continue;
				}
				dfs(step+1);
				memcpy(a,b,sizeof(b));
			}
}
signed main()
{
	cin>>n;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*10,ans+=(i-1)*pw[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(0);
	if(minn==1e9) cout<<6;
	else cout<<minn;
	return 0;
}