Advertisement
Josif_tepe

Untitled

Nov 7th, 2021
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n;
  5. int niza[30005];
  6. int dp[30005][3];
  7. int rec(int i, int prev_medal) {
  8.     if(i == n) {
  9.         return 0;
  10.     }
  11.     if(dp[i][prev_medal] != -1) {
  12.         return dp[i][prev_medal];
  13.     }
  14.     int result = 2e9;
  15.     if(prev_medal == 0) {
  16.         result = min(result, rec(i + 1, 0) + (niza[i] != prev_medal));
  17.        
  18.     }
  19.     else if(prev_medal == 1) {
  20.         result = min(result, rec(i + 1, 1) + (niza[i] != prev_medal));
  21.         result = min(result, rec(i + 1, 0) + (niza[i] != prev_medal));
  22.        
  23.     }
  24.     else if(prev_medal == 2) {
  25.         result = min(result, rec(i + 1, 2) + (niza[i] != prev_medal));
  26.         result = min(result, rec(i + 1, 1) + (niza[i] != prev_medal));
  27.         result = min(result, rec(i + 1, 0) + (niza[i] != prev_medal));
  28.     }
  29.     dp[i][prev_medal] = result;
  30.     return result;
  31. }
  32. int main()
  33. {
  34.     cin >> n;
  35.     for(int i = 0; i < n; i++) {
  36.         cin >> niza[i];
  37.         niza[i]--;
  38.         dp[i][0] = dp[i][1] = dp[i][2] = -1;
  39.     }
  40.     int answer = 2e9;
  41.     for(int i = 0; i <= 2; i++) {
  42.         answer = min(answer, rec(0, i));
  43.     }
  44.     for(int i = 0; i < n; i++) {
  45.         dp[i][0] = dp[i][1] = dp[i][2] = -1;
  46.     }
  47.     reverse(niza, niza + n);
  48.     for(int i = 0; i <= 2; i++) {
  49.         answer = min(answer, rec(0, i));
  50.     }
  51.     cout << answer << endl;
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement