#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
char arr[405];
vector<int> r,g,y;
int memo[205][205][205][3];
const int INF=1000000000;
int dp(int sr,int sg,int sy,int last){ ///1000000000 for invalid case
if (!sr && !sg && !sy) return 0;
else if (memo[sr][sg][sy][last]!=-1) return memo[sr][sg][sy][last];
int ans=INF,pos=sr+sg+sy-1;
if (last!=0 && sr) ans=min(ans,dp(sr-1,sg,sy,0)+abs(pos-r[sr-1]));
if (last!=1 && sg) ans=min(ans,dp(sr,sg-1,sy,1)+abs(pos-g[sg-1]));
if (last!=2 && sy) ans=min(ans,dp(sr,sg,sy-1,2)+abs(pos-y[sy-1]));
return memo[sr][sg][sy][last]=ans;
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&n);
getchar();
for (int x=0;x<n;x++){
arr[x]=getchar();
if (arr[x]=='R') r.push_back(x);
else if (arr[x]=='G') g.push_back(x);
else y.push_back(x);
}
memset(memo,-1,sizeof(memo));
int ans=INF;
if (!r.empty()) ans=min(ans,dp(r.size()-1,g.size(),y.size(),0)+abs(n-1-r.back()));
if (!g.empty()) ans=min(ans,dp(r.size(),g.size()-1,y.size(),1)+abs(n-1-g.back()));
if (!y.empty()) ans=min(ans,dp(r.size(),g.size(),y.size()-1,2)+abs(n-1-y.back()));
printf("%d\n",(ans==INF)?-1:(ans>>1));
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
101496 KB |
Output is correct |
2 |
Correct |
80 ms |
101496 KB |
Output is correct |
3 |
Correct |
79 ms |
101624 KB |
Output is correct |
4 |
Correct |
79 ms |
101496 KB |
Output is correct |
5 |
Correct |
81 ms |
101496 KB |
Output is correct |
6 |
Correct |
93 ms |
101496 KB |
Output is correct |
7 |
Correct |
78 ms |
101472 KB |
Output is correct |
8 |
Correct |
78 ms |
101424 KB |
Output is correct |
9 |
Correct |
78 ms |
101496 KB |
Output is correct |
10 |
Correct |
78 ms |
101496 KB |
Output is correct |
11 |
Incorrect |
79 ms |
101372 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
101496 KB |
Output is correct |
2 |
Correct |
80 ms |
101496 KB |
Output is correct |
3 |
Correct |
79 ms |
101624 KB |
Output is correct |
4 |
Correct |
79 ms |
101496 KB |
Output is correct |
5 |
Correct |
81 ms |
101496 KB |
Output is correct |
6 |
Correct |
93 ms |
101496 KB |
Output is correct |
7 |
Correct |
78 ms |
101472 KB |
Output is correct |
8 |
Correct |
78 ms |
101424 KB |
Output is correct |
9 |
Correct |
78 ms |
101496 KB |
Output is correct |
10 |
Correct |
78 ms |
101496 KB |
Output is correct |
11 |
Incorrect |
79 ms |
101372 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
101468 KB |
Output is correct |
2 |
Correct |
79 ms |
101468 KB |
Output is correct |
3 |
Correct |
81 ms |
101496 KB |
Output is correct |
4 |
Correct |
82 ms |
101556 KB |
Output is correct |
5 |
Correct |
82 ms |
101496 KB |
Output is correct |
6 |
Correct |
75 ms |
101496 KB |
Output is correct |
7 |
Correct |
76 ms |
101496 KB |
Output is correct |
8 |
Correct |
76 ms |
101524 KB |
Output is correct |
9 |
Correct |
79 ms |
101500 KB |
Output is correct |
10 |
Correct |
81 ms |
101624 KB |
Output is correct |
11 |
Correct |
80 ms |
101496 KB |
Output is correct |
12 |
Correct |
76 ms |
101496 KB |
Output is correct |
13 |
Correct |
78 ms |
101496 KB |
Output is correct |
14 |
Correct |
79 ms |
101436 KB |
Output is correct |
15 |
Correct |
80 ms |
101496 KB |
Output is correct |
16 |
Correct |
88 ms |
101496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
79 ms |
101496 KB |
Output is correct |
2 |
Correct |
80 ms |
101496 KB |
Output is correct |
3 |
Correct |
79 ms |
101624 KB |
Output is correct |
4 |
Correct |
79 ms |
101496 KB |
Output is correct |
5 |
Correct |
81 ms |
101496 KB |
Output is correct |
6 |
Correct |
93 ms |
101496 KB |
Output is correct |
7 |
Correct |
78 ms |
101472 KB |
Output is correct |
8 |
Correct |
78 ms |
101424 KB |
Output is correct |
9 |
Correct |
78 ms |
101496 KB |
Output is correct |
10 |
Correct |
78 ms |
101496 KB |
Output is correct |
11 |
Incorrect |
79 ms |
101372 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |