fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define INF 1000000000
  4. #define MOD 1000000007
  5. #define EPS 0.00000001
  6. #define MAXN 1000005
  7. #define ins insert
  8. #define pb push_back
  9. #define mp make_pair
  10. #define sz size
  11. #define rep(i, n) for(int i = 0; i < n; ++i)
  12. #define sd(n) scanf("%d",&n)
  13. #define sll(n) scanf("%I64d",&n)
  14. #define pdn(n) printf("%d\n",n)
  15. #define plln(n) printf("%I64d\n",n)
  16. #define pd(n) printf("%d ",n)
  17. #define nl() printf("\n")
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef vector<int> vi;
  23. typedef vector<vi> vii;
  24. typedef pair<int, int> pii;
  25.  
  26. int n, k; string s;
  27.  
  28. int dp[500005][27];
  29.  
  30. int solve(int idx, char prev) {
  31. 	if(idx == 0) {
  32. 		if(prev == s[idx])
  33. 			return dp[idx][prev-'A'] = 1;
  34. 		return dp[idx][prev-'A'] = 0;
  35. 	}
  36. 	if(dp[idx][prev-'A'] != -1)
  37. 		return dp[idx][prev-'A'];
  38. 	if(prev == s[idx]) {
  39. 		int ans = INF;
  40. 		rep(i, k) {
  41. 			if(i+'A' != prev)
  42. 				ans = min(ans, 1+solve(idx-1, i+'A'));
  43. 		}
  44. 		return dp[idx][prev-'A'] = ans;
  45. 	}
  46. 	else {
  47. 		int ans = solve(idx-1, s[idx]);
  48. 		rep(i, k) {
  49. 			if(i+'A' != prev)
  50. 				ans = min(ans, 1+solve(idx-1, i+'A'));
  51. 		}
  52. 		return dp[idx][prev-'A'] = ans;
  53. 	}
  54. }
  55.  
  56. int main() {
  57. 	ios_base::sync_with_stdio(0);
  58. 	cin.tie(0);
  59. 	rep(i, 500005) {
  60. 		rep(j, 27) {
  61. 			dp[i][j] = -1;
  62. 		}
  63. 	}
  64. 	cin >> n >> k >> s;
  65. 	cout << solve(n-1, '[') << endl;
  66. 	return 0;
  67. }
Success #stdin #stdout 0.05s 55968KB
comments (?)
stdin 
6 3
ABBACC
stdout 
2
https://ideone.com/11kNYs
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!