腾讯刷题 假期

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述:

第一行一个整数 表示放假天数

第二行 n 个数 每个数为0或1,第 i 个数表示公司在第 i 天是否营业

第三行 n 个数 每个数为0或1,第 i 个数表示健身房在第 i 天是否营业

（1为营业 0为不营业）

输出描述:

一个整数，表示小Q休息的最少天数

输入例子1:

4

1 1 0 0

0 1 1 0

输出例子1:

2

例子说明1: 小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天

通过题意，我们了解到，当小Q在当天工作时，前一天一定是在锻炼或者休息；当小Q当天锻炼时，前一天一定是在工作或者休息，于是可以用动态规划来完成，首先使用一个二维数组来存放前几天最多工作或者锻炼的天数，一次来不断累加，最后求出小Q最多不休息的天数，减去即可得到最少休息天数。

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

int work[100001], sport[100001], dp[100001][2];

int main()
{
    int n, i;
    scanf("%d", &n);
    for(i = 1;i <= n;i++)
    {
        scanf("%d", &work[i]);
    }
    for(i = 1;i <= n;i++)
    {
        scanf("%d", &sport[i]);
    }
    for(i = 1;i <= n;i++)
    {
        dp[i][0] = max(dp[i-1][1]+work[i], dp[i-1][0]);
        dp[i][1] = max(dp[i-1][0]+sport[i], dp[i-1][1]);
    }
    printf("%d\n", n-max(dp[n][0], dp[n][1]));
    return 0;
}