Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- int dp[30005][3];
- int main()
- {
- int n;
- cin >> n;
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- v[i]--;
- dp[i][0] = dp[i][1] = dp[i][2] = 2e9;
- }
- int result = 2e9;
- dp[0][0] = (v[0] != 0);
- dp[0][1] = (v[0] != 1);
- dp[0][2] = (v[0] != 2);
- for(int i = 1; i < n; i++) {
- for(int j = 0; j <= 2; j++) {
- for(int k = 0; k <= j; k++) {
- dp[i][k] = min(dp[i][k], dp[i - 1][j] + (v[i] != k));
- }
- }
- }
- result = min(result, dp[n - 1][0]);
- result = min(result, dp[n - 1][1]);
- result = min(result, dp[n - 1][2]);
- for(int i = 0; i < n; i++) {
- dp[i][0] = dp[i][1] = dp[i][2] = 2e9;
- }
- reverse(v.begin(), v.end());
- dp[0][0] = (v[0] != 0);
- dp[0][1] = (v[0] != 1);
- dp[0][2] = (v[0] != 2);
- for(int i = 1; i < n; i++) {
- for(int j = 0; j <= 2; j++) {
- for(int k = 0; k <= j; k++) {
- dp[i][k] = min(dp[i][k], dp[i - 1][j] + (v[i] != k));
- }
- }
- }
- result = min(result, dp[n - 1][0]);
- result = min(result, dp[n - 1][1]);
- result = min(result, dp[n - 1][2]);
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement