Guest User

Untitled

a guest
Jun 30th, 2017
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2. #define ll long long
  3. using namespace std;
  4. ll n, a[105];
  5. ll dp[3][3][105];
  6.  
  7. // last day done (gym isg = 1) contest (isc = 1) else 0;
  8.  
  9. ll f(ll isg, ll isc, ll day){
  10.     if(day == n) return 0;
  11.     if(dp[isg][isc][day] != -1) return dp[isg][isc][day];
  12.     if(a[day] == 0){
  13.         return dp[isg][isc][day] = 1 + f(0, 0, day+1);
  14.     }
  15.     else if(a[day] == 1){
  16.         if(isc == 0) return dp[isg][isc][day] = min(f(0, 1, day+1), 1 + f(0, 0, day+1));
  17.         else return dp[isg][isc][day] = 1 + f(0, 0, day+1);
  18.     }
  19.     else if(a[day] == 2){
  20.         if(isg == 0) return dp[isg][isc][day] = min(f(1, 0, day+1), 1 + f(0, 0, day+1));
  21.         else return dp[isg][isc][day] = 1 + f(0, 0, day+1);
  22.     }
  23.     else if(a[day] == 3){
  24.         if(!isg && !isc) return dp[isg][isc][day] = min(f(1, 0, day+1),  f(0, 1, day+1));
  25.         else if(!isg) return dp[isg][isc][day] = min(f(1, 0, day+1), 1 + f(0, 0, day+1));
  26.         else return dp[isg][isc][day] = min(f(0, 1, day+1), 1 + f(0, 0, day+1));
  27.     }
  28. }
  29.  
  30. int main(){
  31.     cin >> n;
  32.     memset(dp, -1, sizeof dp);
  33.     for(int i = 0; i < n; i++) cin >> a[i];
  34.     cout << f(0, 0, 0);
  35.     return 0;
  36. }
Add Comment
Please, Sign In to add comment