Advertisement
Josif_tepe

Untitled

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