前言
第一题签到之后就睡麻了，这题都没想出来，满脑子都是区间DP，没救了。
题目
\(\rm 128MB,1s.\)
无题目链接。
题目大意：
炉石传说最近出了一个新模式：佣兵模式。
虽然我一度觉得这个模式完全没有天梯有意思，没有技术含量，还要高额氪金，但是架不住高额的任务奖励，还是打了两轮，只能说暴雪开始摆烂了。
在这个模式中，玩家控制的佣兵分为红绿蓝三种颜色，具有克制关系：红色克制绿色，绿色克制蓝色，蓝色克制红色，克制可以造成双倍伤害。
现在有一个只有 RGY 三种字符的字符串，表示这些佣兵，为了让比赛更好看，你决定让相邻的佣兵不是相同的类型，你可以执行以下操作任意次数：
- 选择两个相邻的佣兵，交换他们。
询问达到目的的最少操作次数，如果不能达到目的，输出 -1。
\(1\le n\le 400.\)
讲解
先判断无解：其中一种佣兵个数超过 \(\lceil \frac{n}{2}\rceil\)。
再挖掘性质：相同颜色的佣兵相对顺序不会改变。
然后我们直接枚举最终状态即可。
令 \(dp_{i,j,k,0/1/2}\) 表示三种颜色的个数，最后一个颜色是谁，直接 \(\tt dp\) 转移即可。
由于空间不够，我用了鸽巢原理卡空间，时间复杂度 \(O(n^3)\)。
代码
打出来就过，完全不用调试的代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 405;
const int INF = 0x3f3f3f3f;
int n;
int dp[MAXN][134][134][3];
int ID[256],cnt[3],pos[3][MAXN],tot[3];
char a[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
void ckmin(int &x,int y){x = Min(x,y);}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); scanf("%s",a+1);
for(int i = 1;i <= n;++ i)
if(a[i] == 'R') ++cnt[0];
else if(a[i] == 'G') ++cnt[1];
else if(a[i] == 'Y') ++cnt[2];
if(Max(Max(cnt[0],cnt[1]),cnt[2]) > (n+1)/2) {Put(-1,'\n');return 0;}
if(cnt[0] > 133) ID['G'] = 0,ID['Y'] = 1,ID['R'] = 2;
else if(cnt[1] > 133) ID['R'] = 0,ID['Y'] = 1,ID['G'] = 2;
else ID['R'] = 0,ID['G'] = 1,ID['Y'] = 2;
for(int i = 1;i <= n;++ i) pos[ID[a[i]]][++tot[ID[a[i]]]] = i;
memset(dp,0x3f,sizeof(dp));
if(tot[0]) dp[1][1][0][0] = pos[0][1]-1;
if(tot[1]) dp[1][0][1][1] = pos[1][1]-1;
if(tot[2]) dp[1][0][0][2] = pos[2][1]-1;
for(int i = 1;i < n;++ i)
for(int j = 0;j <= i && j <= tot[0];++ j)
for(int k = 0;j+k <= i && k <= tot[1];++ k)
{
if(i-j-k > tot[2]) continue;
for(int y = 0;y < 3;++ y)
for(int l = 0;l < 3;++ l)
{
if(y == l) continue;
if(!l)
{
if(j == tot[0]) continue;
ckmin(dp[i+1][j+1][k][l],dp[i][j][k][y]+Max(0,pos[0][j+1]-(i+1)));
}
else if(l == 1)
{
if(k == tot[1]) continue;
ckmin(dp[i+1][j][k+1][l],dp[i][j][k][y]+Max(0,pos[1][k+1]-(i+1)));
}
else
{
if(i-j-k == tot[2]) continue;
ckmin(dp[i+1][j][k][l],dp[i][j][k][y]+Max(0,pos[2][i+1-j-k]-(i+1)));
}
}
}
int ans = INF;
for(int i = 0;i < 3;++ i) ans = Min(ans,dp[n][tot[0]][tot[1]][i]);
Put(ans,'\n');
return 0;
}