题解 P6116 [JOI 2019 Final]たのしいたのしいたのしい家庭菜園
tytyty
·
·
题解
CYJian 学长的 NOIP2020 模拟赛题，只有题面被魔改了（不过也是搬花盆）。但是蒟蒻考场只会做特殊性质 QwQ。
题意
给定一个由 R,G,Y 组成的，长度为 n 的字符串，每次只能交换相邻两个字符，问最少操作几次，能使相邻两个字符不同。若无解，输出 -1。
Solution
$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;
}
```