Advertisement
Josif_tepe

Untitled

Nov 7th, 2021
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 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.     for(int j = 0; j <= prev_medal; j++) {
  16.         result = min(result, rec(i + 1, j) + (niza[i] != prev_medal));
  17.     }
  18.     dp[i][prev_medal] = result;
  19.     return result;
  20. }
  21. int main()
  22. {
  23.     cin >> n;
  24.     for(int i = 0; i < n; i++) {
  25.         cin >> niza[i];
  26.         niza[i]--;
  27.         dp[i][0] = dp[i][1] = dp[i][2] = -1;
  28.     }
  29.     int answer = 2e9;
  30.     for(int i = 0; i <= 2; i++) {
  31.         answer = min(answer, rec(0, i));
  32.     }
  33.     for(int i = 0; i < n; i++) {
  34.         dp[i][0] = dp[i][1] = dp[i][2] = -1;
  35.     }
  36.     reverse(niza, niza + n);
  37.     for(int i = 0; i <= 2; i++) {
  38.         answer = min(answer, rec(0, i));
  39.     }
  40.     cout << answer << endl;
  41.     return 0;
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement