이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 444;
const int inf = 1e9;
int n;
string s;
int a[maxn];
map<vector<int>,int> dp[maxn][6];
int solve(int i, int last, vector<int> hold) {
if (i==n) {
int have = -1;
for (int j=0; j<3; j++) {
if (hold[j] > 1) return inf;
if (hold[j] == 1) {
if (~have) return inf;
have = j;
}
}
if (have == last) return inf;
return 0;
} else {
int sum = accumulate(hold.begin(), hold.end(), 0);
if (dp[i][last].count(hold)) return dp[i][last][hold];
int res = inf;
// do nothing
if (a[i] != last) {
res = min(res, sum+solve(i+1,a[i],hold));
}
// drop elem
{
for (int j=0; j<3; j++) {
if (hold[j]>0 && last!=j && a[i]!=j) {
auto nhold = hold;
nhold[j]--;
res = min(res, sum-1 + solve(i+1,a[i],nhold));
}
}
}
// take elem
{
auto nhold = hold;
nhold[a[i]]++;
res = min(res, sum+solve(i+1,last,nhold));
}
// drop elem and take elem
{
for (int j=0; j<3; j++) {
if (hold[j]>0 && last!=j) {
auto nhold = hold;
nhold[j]--;
nhold[a[i]]++;
res = min(res, sum + solve(i+1,j,nhold));
}
}
}
return dp[i][last][hold] = res;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
cin>>s;
for (int i=0; i<n; i++) {
if (s[i]=='R') {
a[i]=0;
} else if (s[i]=='G') {
a[i]=1;
} else if (s[i]=='Y') {
a[i]=2;
} else assert(false);
}
int res = solve(0,4,{0,0,0});
if (res > inf/2) res = -1;
cout<<res<<endl;
return 0;
}
# | 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... |