#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define mod 1000000007
#define inf 1000000009
#define N 4005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, a[N], dp[N][N][5][5];
map < char , int > h;
int f(int bas, int son, int d1, int d2){
if(bas == son)
return (a[bas] != d1 and a[bas] != d2)?0:inf;
if(bas > son)
return (d1 != d2)?0:inf;
int &r = dp[bas][son][d1][d2];
if(r != -1)
return r;
r = inf;
if(a[bas] != d1)
r = min(r, f(bas + 1, son, a[bas], d2));
if(a[son] != d2)
r = min(r, f(bas, son - 1, d1, a[son]));
// if(a[son] != d1 and a[bas] != d2)
// r = min(r, f(bas + 1, son - 1, a[son], a[bas]) + 1);
for(int i = bas + 1; i <= son; i++)
// if(a[i] != d1)
r = min(r, f(bas, i - 1, a[i], a[i + 1]) + f(i + 1, son, a[i - 1], d2) + i - bas);
for(int i = bas; i < son; i++)
// if(a[i] != d2)
r = min(r, f(bas, i - 1, d1, a[i + 1]) + f(i + 1, son, a[i - 1], a[i]) + son - i);
// cout << bas << " " << son << " " << d1 << " " << d2 << " -> " << r << endl;
return r;
}
int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(dp, -1, sizeof dp);
h['R'] = 1;
h['G'] = 2;
h['Y'] = 3;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
char x;
scanf(" %c",&x);
a[i] = h[x];
}
// for(int i = 1; i <= n; i++)cout << a[i] << " ";cout << endl;
if(f(1, n, 0, 0) >= inf)
printf("-1\n");
else
printf("%d\n", f(1, n, 0, 0));
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
907 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
907 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
851 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
907 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
