이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 405
#define INF 2000000000
using namespace std;
int n,dp[N][N][N][4], rs[N], gs[N], ys[N];
string s;
int cost(int r, int g, int y, int i) {
return abs(rs[i]-r)+abs(gs[i]-g)+abs(ys[i]-y);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
for(int i = 1; i <= n; i ++) {
rs[i] = rs[i-1]+(s[i-1]=='R');
gs[i] = gs[i-1]+(s[i-1]=='G');
ys[i] = ys[i-1]+(s[i-1]=='Y');
}
for(auto&i: dp) for(auto&j: i) for(auto&k: j) for(auto&l: k) l = INF;
dp[0][0][0][0] = 0;
for(int i = 0; i < n; i ++) {
for(int r = 0; r <= i && r <= rs[n]; r ++) {
for(int g = 0; r+g <= i && g <= gs[n]; g ++) {
int y = i-r-g;
if(y > ys[n]) continue;
for(int t = (i!=0); t <= 3; t ++) {
if(t != 1)
dp[i+1][r+1][g][1] = min(dp[i+1][r+1][g][1],dp[i][r][g][t]+cost(r+1,g,y,i+1));
if(t != 2)
dp[i+1][r][g+1][2] = min(dp[i+1][r][g+1][2],dp[i][r][g][t]+cost(r,g+1,y,i+1));
if(t != 3)
dp[i+1][r][g][3] = min(dp[i+1][r][g][3],dp[i][r][g][t]+cost(r,g,y+1,i+1));
}
}
}
}
// cout << dp[2][1][0][1] << "\n";
// cout << dp[3][1][0][3] << "\n";
// cout << dp[4][2][0][1] << "\n";
// cout << dp[5][2][0][3] << "\n";
// cout << dp[6][2][1][2] << "\n";
int res = min({dp[n][rs[n]][gs[n]][1],dp[n][rs[n]][gs[n]][2],dp[n][rs[n]][gs[n]][3]})/2;
assert(res%2==0);
if(res == INF/2) cout << -1;
else cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |