Josif_tepe

Untitled

Nov 5th, 2025
479
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int maxn = 30005;
  7. const int INF = 2e9;
  8. int n, a[maxn];
  9. int dp[maxn][4];
  10. int rec(int at, int medal) {
  11.     if(at == n) {
  12.         return 0;
  13.     }
  14.     if(dp[at][medal] != -1) {
  15.         return dp[at][medal];
  16.     }
  17.     int res = INF;
  18.    
  19.     if(medal == 1) {
  20.         for(int new_medal = 1; new_medal <= 3; new_medal++) {
  21.             int promena = 0;
  22.            
  23.             if(medal != a[at]) {
  24.                 promena = 1;
  25.             }
  26.             res = min(res, rec(at + 1, new_medal) + promena);
  27.         }
  28.     }
  29.     else if(medal == 2) {
  30.         for(int new_medal = 2; new_medal <= 3; new_medal++) {
  31.             int promena = 0;
  32.             if(medal != a[at]) {
  33.                 promena = 1;
  34.             }
  35.            
  36.             res = min(res, rec(at + 1, new_medal) + promena);
  37.         }
  38.     }
  39.     else {
  40.         int promena = 0;
  41.         if(medal != a[at]) {
  42.             promena = 1;
  43.         }
  44.         res = min(res, rec(at + 1, 3) + promena);
  45.     }
  46.    
  47.     dp[at][medal] = res;
  48.     return res;
  49. }
  50. int main()
  51. {
  52.     cin >> n;
  53.     for(int i = 0; i < n; i++) {
  54.         cin >> a[i];
  55.     }
  56.    
  57.     memset(dp, -1, sizeof dp);
  58.     int res = INF;
  59.     for(int i = 1; i <= 3; i++) {
  60.         res = min(res, rec(0, i));
  61.     }
  62.    
  63.     reverse(a, a + n);
  64.     memset(dp, -1, sizeof dp);
  65.     for(int i = 1; i <= 3; i++) {
  66.         res = min(res, rec(0, i));
  67.     }
  68.    
  69.     cout << res << endl;
  70.  
  71.      return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment