假期

#include<bits/stdc++.h>
using namespace std;
using LL = int64_t;
const int maxn=1e5+5;
int dp[maxn][3],a[maxn],b[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) {
        dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
        dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][1]);
    }
    cout<<n-max(dp[n][0],dp[n][1]);
    return 0;
}

n = int(input())
a = [int(value) for value in input().split()]
b = [int(value) for value in input().split()]
result = 0
previous_a = 0
previous_b = 0
 
for i in range(n):
    if a[i] == 0 and b[i] == 0:
        result += 1
        previous_a = previous_b = 0
        continue
         
    if a[i] == 1 and b[i] == 0:
        if previous_a == 1:
            result += 1
            previous_a = previous_b = 0
            continue
        else:
            previous_a = 1
            previous_b = 0
            continue
             
    if a[i] == 0 and b[i] == 1:
        if previous_b == 1:
            result += 1
            previous_a = previous_b = 0
            continue
        else:
            previous_a = 0
            previous_b = 1
            continue
     
    if a[i] == 1 and b[i] == 1:
        if previous_a == 1:
            previous_a = 0
            previous_b = 1
            continue
        if previous_b == 1:
            previous_b = 0
            previous_a = 1
            continue
        if previous_b == 0 and previous_a == 0:
            continue
print(result)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strIsWorking = br.readLine().trim().split(" ");
        String[] strIsGym = br.readLine().trim().split(" ");
        int[] isWorking = new int[n];
        int[] isGym = new int[n];
        for(int i = 0; i < n; i++){
            isWorking[i] = Integer.parseInt(strIsWorking[i]);
            isGym[i] = Integer.parseInt(strIsGym[i]);
        }
        // dp[i][0],dp[i][1],dp[i][2]分别表示第i天 休息/锻炼/工作 累计的最小休息天数
        int[][] dp = new int[n + 1][3];
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 3; j++) dp[i][j] = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            // 今天健身房开门，锻炼从另外两种状态转移过来
            if(isGym[i - 1] == 1)
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]);
            // 今天单位开门，工作从另外两种状态转移过来
            if(isWorking[i - 1] == 1)
                dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            // 休息可以从自身或另外两种状态转移而来
            dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1;
        }
        System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2])));
    }
}

    let nDayoff = readline();
    let workStr = readline();
    let gymStr = readline();

    let work = workStr.split(' ').map(Number);
    let gym = gymStr.split(' ').map(Number);
    let len = work.length;
    
    let dp = new Array(nDayoff + 1);
    for (let i = 0; i < nDayoff + 1; i++) {
        dp[i] = new Array(3).fill(Infinity);
    }
    //console.log("dp:", dp);

    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (let i = 1; i <= len; i++) {
        if (gym[i - 1] === 1) {
            // 可以锻炼
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]);
        }
        if (work[i - 1] === 1) {
            //可以工作
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]);
        }
        //可以休息
        dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1;
    }
    let res = Math.min(dp[len][0], Math.min(dp[len][1], dp[len][2]));
    console.log(res);

import java.util.Scanner;
public  class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] wo = new int[n];
            for (int i = 0; i < n; i++) {
                wo[i] = in.nextInt();
            }
            int[] ex = new int[n];
            for (int i = 0; i < n; i++) {
                ex[i] = in.nextInt();
            }
            System.out.println(minDay(wo, ex));
        }
    }

  

    public static int minDay(int[] wo, int[] ex) {
        int n = wo.length;
        int[][] dp = new int[n][3];
        // 0 休息，1 健身，2 工作
        dp[0][0] = wo[0] == 0 && ex[0] == 0 ? 1 : 0;
        dp[0][1] = wo[0] == 0 ? Integer.MAX_VALUE : 0;
        dp[0][2] = ex[0] == 0 ? Integer.MAX_VALUE : 0;

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

            dp[i][2] = wo[i] == 1 ? 
                Math.min(dp[i - 1][0], dp[i - 1][1]) : Integer.MAX_VALUE;

            dp[i][1] = ex[i] == 1 ? 
                Math.min(dp[i - 1][0], dp[i - 1][2]) : Integer.MAX_VALUE;

            dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + 1;
        }

        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }
}

day=int(input())
_C=input()
c=[int(i) for i in _C.split()]
_G=input()
g=[int(i) for i in _G.split()]
 
a=[c.copy(),g.copy()]
 
for i in range(day-1):
    if c[i]==0:
        a[0][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i]
    else:
        a[0][i+1]+=a[1][i]
    if g[i]==0:
        a[1][i+1]+=a[0][i] if a[0][i] > a[1][i] else a[1][i]
    else:
        a[1][i+1]+=a[0][i]
 
print(day-(a[0][day-1] if a[0][day-1]>a[1][day-1] else a[1][day-1]))

# include <iostream>
# include <cstdlib>
# include <cstring>
# include <stack>
# define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
 
int main(void){
    int n ;
    while(cin>>n){
        int gym[n],i, work[n];
        for ( i=0; i<n; ++i )
            cin>>work[i];
        for( i=0; i<n; ++i )
            cin>>gym[i];
        int dp[n+1][3]; // 0是休息，1是锻炼，2是工作
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = dp[0][1] = dp[0][2] = 0;
        for ( int i=1; i<=n; ++i ){
            if ( gym[i-1] == 1 ){
                // 可以锻炼
                dp[i][1] = min( dp[i-1][0], dp[i-1][2] );
            }
            if ( work[i-1] == 1 ){
                // 可以工作
                dp[i][2] = min( dp[i-1][0], dp[i-1][1] );
            }
            dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]))+1;
        }
        int res = min(dp[n][0], min(dp[n][1], dp[n][2]));
        cout<<res<<endl;
    }
    return 0;
}

//1. 选择休息，故天数多1
dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) + 1; 
//2. 不休息，选择工作
dp[i][1] = min(dp[i-1][0], dp[i-1][2]); 
//3. 不休息，选择锻炼
dp[i][2] = min(dp[i-1][0], dp[i-1][1]); 
//边界：第0天休息天数为0
dp[0][i] = 0 (i = 1, 2, 3) 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> work(n), slp(n);
	for (int i = 0; i < n; ++i)
		cin >> work[i];
	for (int i = 0; i < n; ++i)
		cin >> slp[i];
	vector<vector<int>> dp(3, vector<int>(n + 1));
	dp[0][0] = dp[1][0] = dp[2][0] = 0;
	for (int i = 1; i <= n; ++i) {
		dp[0][i] = max(dp[0][i - 1], max(dp[1][i - 1], dp[2][i - 1]));
		if (slp[i - 1]) {
			dp[1][i] = max(dp[2][i - 1], dp[0][i - 1]) + 1;
		}
		if (work[i - 1]) {
			dp[2][i] = max(dp[1][i - 1], dp[0][i - 1]) + 1;
		}
	}
	cout << n - max(dp[0][n], max(dp[1][n], dp[2][n])) << endl;

	return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void printLeastRelax(vector<int> &a, vector<int> &b){
    int n = a.size();

    int dp0 = 1;
    int dp1 = a[0] ? 0 : n;
    int dp2 = b[0] ? 0 : n;
    for(int i = 1; i < n; ++i){
        int prev_dp0 = dp0;
        int prev_dp1 = dp1;
        int prev_dp2 = dp2;

        dp0 = min(prev_dp0, min(prev_dp1, prev_dp2)) + 1; 
        dp1 = a[i] ? min(prev_dp0, prev_dp2) : n;
        dp2 = b[i] ? min(prev_dp0, prev_dp1) : n;
    }
    cout << min(dp0, min(dp1, dp2)) << endl;
}

int main() {
    int n;
    vector<int> a;
    vector<int> b;
    
    cin >> n;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        cin >> b[i];
    }

    printLeastRelax(a,b);
}
// 64 位输出请用 printf("%lld")

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] nums1 = new int[n]; // 工作
            int[] nums2 = new int[n]; // 健身
            for (int i = 0; i < n; i++) {
                nums1[i] = in.nextInt();
            }
            for (int i = 0; i < n; i++) {
                nums2[i] = in.nextInt();
            }
            int work = 0;
            for (int i = 0; i < n; i++) {
                if (nums1[i] == 1 && nums2[i] == 1) { // 都为营业，选一个（不必关心具体选哪个）
                    work++;
                } else if (nums1[i] == 1) { // 只营业一个，则就选营业的那个（贪心思想）
                    work++;
                    if (i + 1 < n) nums1[i + 1] = 0; // 选了营业的，就将对应的明天的营业状态置为0（因为不能两天选一家）
                } else if (nums2[i] == 1) {
                    work++;
                    if (i + 1 < n) nums2[i + 1] = 0;
                }
            }
            System.out.println(n - work);
        }
    }
}

package tencent;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] c = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y[i] = scanner.nextInt();
        }
        backtrack(-1, c, y, 0, n, 0);
        System.out.println(min);
    }

    /**
     * 回溯法解决问题，只有两种选择
     *
     * @param last  上一个选择，0 代表公司，1 代表健身房
     * @param c     公司列表
     * @param j     健身房列表
     * @param i     当前要进行选择的位置
     * @param n     总共要选择的次数
     * @param cRest 当前已经休息的次数
     */
    public static void backtrack(int last, int[] c, int[] j, int i, int n, int cRest) {
        // 判断是否已经超过了
        if (n == i) {
            if (cRest < min) {
                min = cRest;
            }
            return;
        }

        if (last == -1) {
            // 代表上一次没有选择，其他条件允许情况下可以选择公司或健身房
            if (c[i] == 1) {
                // 选择公司
                backtrack(0, c, j, i + 1, n, cRest);
            }
            if (j[i] == 1) {
                // 选择健身房
                backtrack(1, c, j, i + 1, n, cRest);
            }

            // 选择在家休息
            backtrack(-1, c, j, i + 1, n, cRest + 1);
        } else {
            // 上一次存在选择的情况
            if (last == 0) {
                // 上一次选择了公司
                if (j[i] == 1) {
                    // 选择健身房
                    backtrack(1, c, j, i + 1, n, cRest);
                }
                // 在家休息
                backtrack(-1, c, j, i + 1, n, cRest + 1);
            } else {
                // 上一次选择了健身房
                if (c[i] == 1) {
                    // 选择公司
                    backtrack(0, c, j, i + 1, n, cRest);
                }
                // 在家休息
                backtrack(-1, c, j, i + 1, n, cRest + 1);
            }
        }
    }
}