Vasya有n天假期，每天可以去健身房或者撸代码。她不想连续两天做同种运动（脑力也是运动），但她可以每天当一条咸鱼，给出事件，求解最小的休息天数。

　　

事件　　健身房　　机房

0　　　  关　　　　关

1　　　   关　　　　开

2　　　  开　　　   关

3　　　  开　　　　开

 

很明显的计数和状态转移，用dp解。dp[i][j]代表第i天做j事总计的休息时间

对于j, 0==休息，1==健身，2==代码

当一个状态不能转移到的时候，设值为无穷大。这样由于我们需要min(x,y)操作，所以这个值也就不会用到了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define max(x, y) (x > y ? x : y) 7 #define min(x, y) (x > y ? y : x) 8 #define INF 0x3f3f3f3f 9 #define mod 100000000710 #define Yes printf("Yes\n")11 #define No printf("No\n")12 typedef long long LL;13 using namespace std;14 15 const int maxn = 1e2 + 10;16 int dp[maxn][5];17 int n;18 int a;19 20 int main(int argc, const char * argv[]) {21     scanf("%d", &n);22     memset(dp, 0, sizeof(dp));23     for (int i = 1; i <= n; i++) {24         scanf("%d", &a);25         dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + 1;26         if (a == 1 || a == 3) {27             dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]);28         } else {29             dp[i][2] = INF;30         }31         if (a == 2 || a == 3) {32             dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]);33         } else {34             dp[i][1] = INF;35         }36         37         if (a == 0) {38             dp[i][1] = dp[i][2] = INF;39         }40     }41     printf("%d\n", min(dp[n][0], min(dp[n][1], dp[n][2])));42     return 0;43 }