C++14(g++5.4) 解法, 执行用时: 157ms, 内存消耗: 4472K, 提交时间: 2019-10-29 22:31:00
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline void chkmin(int& x, int y) {
if (y < x)
x = y;
}
inline int read() {
int X = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
w = -1;
c = getchar();
}
while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 400 + 10;
const int inf = 0x3f3f3f3f;
int n, a[N];
char s[N];
int cnt[N], pos[3][N], sum[3][N];
int dp[2][N][N][3];
inline int cost(int x, int y, int z, int k) {
int p = x + y + z + 1;
if (x > cnt[0] || y > cnt[1] || z > cnt[2])
return inf;
if (k == 0) {
if (x + 1 > cnt[0])
return inf;
int q = pos[0][x + 1];
return q - p + max(0, y - sum[1][q]) + max(0, z - sum[2][q]);
}
if (k == 1) {
if (y + 1 > cnt[1])
return inf;
int q = pos[1][y + 1];
return q - p + max(0, x - sum[0][q]) + max(0, z - sum[2][q]);
}
if (k == 2) {
if (z + 1 > cnt[2])
return inf;
int q = pos[2][z + 1];
return q - p + max(0, x - sum[0][q]) + max(0, y - sum[1][q]);
}
}
int main() {
n = read();
scanf("%s", s + 1);
if (n == 1) {
puts("0");
return 0;
}
for (re int i = 1; i <= n; ++i) {
if (s[i] == 'R')
a[i] = 0, pos[0][++cnt[0]] = i;
if (s[i] == 'G')
a[i] = 1, pos[1][++cnt[1]] = i;
if (s[i] == 'Y')
a[i] = 2, pos[2][++cnt[2]] = i;
for (re int j = 0; j < 3; ++j) sum[j][i] = sum[j][i - 1] + (a[i] == j);
}
memset(dp, 0x3f, sizeof(dp));
dp[1][0][0][0] = pos[0][1] - 1;
dp[1][1][0][1] = pos[1][1] - 1;
dp[1][0][1][2] = pos[2][1] - 1;
for (re int i = 2; i <= n; ++i) {
int now = i & 1, pre = now ^ 1;
memset(dp[now], 0x3f, sizeof(dp[now]));
for (re int j = 0; j <= min(i, (i + 1) >> 1); ++j)
for (re int k = 0; k <= min(i - j, (i + 1) >> 1); ++k) {
if (i - j - k) {
int w = cost(i - j - k - 1, j, k, 0);
chkmin(dp[now][j][k][0], dp[pre][j][k][1] + w);
chkmin(dp[now][j][k][0], dp[pre][j][k][2] + w);
}
if (j) {
int w = cost(i - j - k, j - 1, k, 1);
chkmin(dp[now][j][k][1], dp[pre][j - 1][k][0] + w);
chkmin(dp[now][j][k][1], dp[pre][j - 1][k][2] + w);
}
if (k) {
int w = cost(i - j - k, j, k - 1, 2);
chkmin(dp[now][j][k][2], dp[pre][j][k - 1][0] + w);
chkmin(dp[now][j][k][2], dp[pre][j][k - 1][1] + w);
}
}
}
int ans = inf;
for (re int i = 0; i <= (n + 1) >> 1; ++i)
for (re int j = 0; j <= min(n - i, (n + 1) >> 1); ++j)
for (re int k = 0; k < 3; ++k) chkmin(ans, dp[n & 1][i][j][k]);
printf("%d\n", ans == inf ? -1 : ans);
return 0;
}
C++(clang++11) 解法, 执行用时: 56ms, 内存消耗: 4368K, 提交时间: 2020-11-20 19:33:17
#include<bits/stdc++.h>
using namespace std;
const int N=405;
char s[N];
int n,ans,cnt[3],g[N][3],pos[N][3],dp[2][N][N][3];
inline int id(char x){if(x=='R') return 0;if(x=='G') return 1;return 2;}
int main()
{
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;++i){int x=id(s[i]);for(int j=0;j<=2;++j) g[i][j]=g[i-1][j];g[i][x]++;pos[++cnt[x]][x]=i;}
memset(dp,0x3f,sizeof(dp));ans=dp[0][0][0][0];
for(int i=0;i<=2;++i) dp[0][0][0][i]=0;
for(int i=1,x=1,y=0;i<=n;++i,x^=1,y^=1)
{
memset(dp[x],0x3f,sizeof(dp[x]));
for(int j=min(i,cnt[0]);j>=0;--j)
for(int k=min(i-j,cnt[1]);k>=0;--k)
{
if(i-j-k>cnt[2]) break;
if(j) dp[x][j][k][0]=min(dp[y][j-1][k][1],dp[y][j-1][k][2])+max(0,g[pos[j][0]][1]-k)+max(0,g[pos[j][0]][2]-(i-j-k));
if(k) dp[x][j][k][1]=min(dp[y][j][k-1][0],dp[y][j][k-1][2])+max(0,g[pos[k][1]][0]-j)+max(0,g[pos[k][1]][2]-(i-j-k));
if(i-j-k) dp[x][j][k][2]=min(dp[y][j][k][0],dp[y][j][k][1])+max(0,g[pos[i-j-k][2]][0]-j)+max(0,g[pos[i-j-k][2]][1]-k);
}
}
for(int i=0;i<=2;++i) ans=min(ans,dp[n&1][cnt[0]][cnt[1]][i]);
printf("%d",ans!=dp[0][n][n][0]?ans:-1);
}
。每个花盆中有一株Joy草。)
，然后交换花盆i和花盆i+1。