Advertisement
Josif_tepe

Untitled

Dec 1st, 2021
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int dp[30005][4];
  7. int n;
  8. vector<int>v;
  9. int rec(int i, int type){
  10.     if(i==n){
  11.         return 0;
  12.     }
  13.  
  14.     if(dp[i][type]!=-1){
  15.         return(dp[i][type]);
  16.     }
  17.  
  18.     int result=1000000000;
  19.  
  20.     if(type==3){
  21.         int greska=0;
  22.         if(v[i]!=type){
  23.             greska=1;
  24.         }
  25.         result=min(result, rec(i+1, 3)+greska);
  26.         result=min(result, rec(i+1, 2)+greska);
  27.         result=min(result, rec(i+1, 1)+greska);
  28.     }
  29.     if(type==2){
  30.         int greska=0;
  31.         if(v[i]!=type){
  32.             greska=1;
  33.         }
  34.         result=min(result, rec(i+1, 2)+greska);
  35.         result=min(result, rec(i+1, 1)+greska);
  36.     }
  37.     if(type==1){
  38.         int greska=0;
  39.         if(v[i]!=type){
  40.             greska=1;
  41.         }
  42.         result=min(result, rec(i+1, 1)+greska);
  43.     }
  44.     dp[i][type]=result;
  45.     return(result);
  46. }
  47. int main()
  48. {
  49.         cin>>n;
  50.         for(int i=0; i<n; i++){
  51.             int a;
  52.             cin>>a;
  53.             v.push_back(a);
  54.         }
  55.  
  56.         for(int i=0; i<n; i++){
  57.                 for(int j=0; j<4; j++){
  58.             dp[i][j]=-1;
  59.             }
  60.         }
  61.  
  62.     int au=rec(0, 1);
  63.     int srebro=rec(0, 2);
  64.     int bronza=rec(0, 3);
  65.  
  66.     int rez = min(au, min(srebro, bronza));
  67.    
  68.     reverse(v.begin(), v.end());
  69.     for(int i=0; i<n; i++){
  70.             for(int j=0; j<4; j++){
  71.         dp[i][j]=-1;
  72.         }
  73.     }
  74.  
  75.  
  76.     au=rec(0, 1);
  77.     srebro=rec(0, 2);
  78.     bronza=rec(0, 3);
  79.     rez = min(min(rez, au), min(srebro, bronza));
  80.     cout << rez << endl;
  81.    
  82.     return 0;
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement