fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mxN=400;
  5. int n, dp[2][8][mxN+1][4], b[mxN][7];
  6. string s;
  7.  
  8. int main() {
  9. 	ios::sync_with_stdio(0);
  10. 	cin.tie(0);
  11.  
  12. 	cin >> n >> s;
  13. 	for(char &c : s)
  14. 		c=(c>'G')+(c>'R');
  15. 	for(int i=0; i<n; ++i) {
  16. 		if(i)
  17. 			memcpy(b[i], b[i-1], sizeof(b[0]));
  18. 		for(int j=1; j<7; ++j)
  19. 			if(j>>s[i]&1)
  20. 				b[i][j]=s[i];
  21. 	}
  22. 	memset(dp, 0x3f, sizeof(dp[0]));
  23. 	dp[0][1<<s[0]][1][3]=0;
  24. 	auto tm=[](int &a, int b) {
  25. 		a=min(a, b);
  26. 	};
  27. 	for(int i=1; i<n; ++i) {
  28. 		memset(dp[i&1], 0x3f, sizeof(dp[0]));
  29. 		for(int j=1; j<7; ++j) {
  30. 			for(int k=1; k<=i; ++k) {
  31. 				for(int l=0; l<4; ++l) {
  32. 					tm(dp[i&1][j|1<<s[i]][k+1][l], dp[i&1^1][j][k][l]);
  33. 					if(j>>s[i]&1)
  34. 						continue;
  35. 					if(l!=s[i])
  36. 						tm(dp[i&1][j][k][s[i]], dp[i&1^1][j][k][l]+k);
  37. 					if(k>1)
  38. 						tm(dp[i&1][j][k-1][s[i]], dp[i&1^1][j][k][l]+k-1);
  39. 					else
  40. 						tm(dp[i&1][1<<s[i]][1][b[i-1][j]], dp[i&1^1][j][1][l]);
  41. 				}
  42. 			}
  43. 		}
  44. 	}
  45. 	int ans=1e9;
  46. 	for(int i=1; i<5; ++i)
  47. 		for(int j=0; j<4; ++j)
  48. 			ans=min(dp[n&1^1][i][1][j], ans);
  49. 	cout << (ans>=1e9?-1:ans);
  50. }
Success #stdin #stdout 0s 15344KB
comments (?)
stdin
copy 
20
YYGYYYGGGGRGYYGRGRYG
stdout
copy 
8
https://ideone.com/rmvMsI
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!