Advertisement
Josif_tepe

Untitled

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