自动搬运

查看原文

来自洛谷，原作者为

	tytyty **

搬运于2025-08-24 22:17:34，当前版本为作者最后更新于2022-11-06 15:27:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

CYJian 学长的 NOIP2020 模拟赛题，只有题面被魔改了（不过也是搬花盆）。但是蒟蒻考场只会做特殊性质 QwQ。

题意

给定一个由 R,G,Y 组成的，长度为 $n$ 的字符串，每次只能交换相邻两个字符，问最少操作几次，能使相邻两个字符不同。若无解，输出 -1。

Solution

$15pts$：

$N\leq 15$ 枚举末状态即可。

$20pts$：

考虑特殊性质的末状态只有两种：RGRGRG 和 GRGRGR。可以发现规律：答案为所有不在最终位置上的 R 与最近的不在位置上的 G 中间间隔数 $+1$ 之和。

$80pts$：

$N\leq 60$ 不能再枚举了考虑，dp。

首先，能发现性质：

1. 当一种颜色的数量大于 $\frac{n}{2}$ 时无解。

2. 交换同种颜色无意义。

3. 假设按原字符串给每个字符编号，相同字符的内部顺序不变。

令 $R\to0,G\to1,Y\to2$。

设 $f_{i,j,k,l,0/1/2}$ 表示前 $i$ 位中有 $j$ 个 $0$、$k$ 个 $1$、$l$ 个 $2$ 且第 $i$ 位为 $0/1/2$ 的最小交换次数。

以 $f_{i,j,k,l,0}$ 为例，由性质 3 可知，第 $i$ 位上的这个 $0$ 一定是原串的第 $j$ 个 $0$ 移过来的，如果我们能算出此时原串的第 $j$ 个 $0$ 的位置 $w$，那么转移就是 $f_{i,j,k,l,0}=\max(f_{i-1,j-1,k,l,1},f_{i-1,j-1,k,l,2})+(w-i)$。

考虑 $w$ 怎么求，首先找到原串中第 $j$ 个 $0$ 的位置 $p$，在状态 $f_{i,j,k,l,0}$ 时，共有 $k$ 个 $1$，$l$ 个 $2$，若 $p$ 之前有足够的 $1,2$ 那么第 $j$ 个 $0$ 的位置是不会变的，否则则需要把 $p$ 之后的 $1,2$ 前移，第 $j$ 个 $0$ 会被挤到更靠后的位置（可能要理解一下）。

我们记前 $i$ 位中有 $sum_{i,1}$ 个 $1$，$sum_{i,2}$ 个 $2$，则 $w=p+\max(0,k-sum_{p,1})+\max(0,l-sum_{p,2})$。

$100pts$：

$N\leq 400$，上面的状态是 $O(n^4)$ 的，考虑优化：$l=i-j-k$ 可以优化掉一维，然后滚动数组可以滚掉一维。

✿ヽ(°▽°)ノ✿完结撒花啦！

Code

#include<bits/stdc++.h>
using namespace std;
const int N=405;
int n,id;
int pos[N][3],sum[N][3],c0,c1,c2;
int f[2][N][N][3];
char s[N];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) {
		if(s[i]=='R') pos[++c0][0]=i;//第 c0 个 0 的位置
		if(s[i]=='G') pos[++c1][1]=i;
		if(s[i]=='Y') pos[++c2][2]=i;
		sum[i][0]=sum[i-1][0]+(s[i]=='R');//前 i 位 0 的数量
		sum[i][1]=sum[i-1][1]+(s[i]=='G');
		sum[i][2]=sum[i-1][2]+(s[i]=='Y');
	}
	memset(f,0x7f,sizeof(f));
	f[1][1][0][0]=pos[1][0]-1;
	f[1][0][1][1]=pos[1][1]-1;
	f[1][0][0][2]=pos[1][2]-1;
	for(int i=2;i<=n;i++) {
		id=(i&1)?1:0;
		for(int j=0;j<=c0;j++) {
			for(int k=0;k<=c1;k++) {
				if(i-j-k>c2) continue;
				if(j>0) {
					int p=pos[j][0];
					int w=p+max(0,k-sum[p][1])+max(0,i-j-k-sum[p][2]);
					f[id][j][k][0]=min(f[id^1][j-1][k][1],f[id^1][j-1][k][2])+w-i;
				}
				if(k>0) {
					int p=pos[k][1];
					int w=p+max(0,j-sum[p][0])+max(0,i-j-k-sum[p][2]);
					f[id][j][k][1]=min(f[id^1][j][k-1][0],f[id^1][j][k-1][2])+w-i;
				}
				if(i-j-k>0) {
					int p=pos[i-j-k][2];
					int w=p+max(0,j-sum[p][0])+max(0,k-sum[p][1]);
					f[id][j][k][2]=min(f[id^1][j][k][0],f[id^1][j][k][1])+w-i;
				}
			}
		}
		memset(f[id^1],0x7f,sizeof(f[id^1]));
	}
	if(n&1) {
		int ans=min(min(f[1][c0][c1][0],f[1][c0][c1][1]),f[1][c0][c1][2]);
		printf("%d",(ans<1e9)?ans:-1);
	}
	else {
		int ans=min(min(f[0][c0][c1][0],f[0][c0][c1][1]),f[0][c0][c1][2]);
		printf("%d",(ans<1e9)?ans:-1);
	}
	return 0;
}