题解 | #假期#

1. 首先这后一天和前一天得许多状态相关，那必然使用动态规划。
2. 假设加验证得思想可以加快解题速度

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int x;

    vector<int> c,fit;
    cin>>n;
    for(int i =0; i< n;i++){
        cin>>x;
        c.push_back(x);
    }

    for(int i =0; i< n;i++){
        cin>>x;
        fit.push_back(x);
    }

    //和前面得状况有关系（3个状态种，到底i天的最大天数，休息日不用加1）
    vector<vector<int>> dp(3,vector<int>(n+1,0));//动归,默认初始化为0

    dp[0][0] = dp[1][0] = dp[2][0] = 0;

    for(int i = 1; i<=n;i++){

        //休息最大天数（后面无需加1）
        dp[0][i] = max(dp[0][i-1],max(dp[1][i-1],dp[2][i-1]));

        if(c[i-1]){
            dp[1][i] = max(dp[0][i-1],dp[2][i-1]) + 1;
        }

        if(fit[i-1]){
            dp[2][i] = max(dp[0][i-1],dp[1][i-1]) + 1;
        }
    }
    //减去最大得就是休息得日子
    cout<<n - max(dp[0][n],max(dp[1][n],dp[2][n]))<<endl;




    return 0;
}