题目描述

难度分:$1400$

输入$n(1 \leq n \leq 100)$和长为$n$的数组$a(0 \leq a[i] \leq 3)$。

有$n$天，第$i$天的情况用$a[i]=0/1/2/3$表示，具体如下：

• 0：健身房关闭，比赛不进行；
• 1：健身房关闭，比赛进行；
• 2：健身房开放，比赛不进行；
• 3：健身房开放，比赛进行。

在每一天，你可以休息、比赛 (如果比赛在这一天进行)，或者做运动 (如果健身房在这一天是开放的)。

但你不想连续两天做同样的活动，这意味着，你不会连续两天做运动，也不会连续两天参加比赛。

输出你休息的最少天数。

输入样例$1$

4
1 3 2 0

输出样例$1$

2

输入样例$2$

7
1 3 3 2 1 2 3

输出样例$2$

0

输入样例$3$

2
2 2

输出样例$3$

1

算法

动态规划

状态定义

$f[i][last]$，从第$i$天开始考虑，且前一天的状态为$last$的情况下，后续能够休息的最少天数。$last=0$表示前一天休息，$last=1$表示前一天比赛，$last=2$表示前一天运动。

状态转移

1. 首先，休息是无条件的，不收任何约束，因此有状态转移方程$f[i][last]=1+f[i+1][0]$。
2. 如果$a[i]$是奇数，是有可能比赛的，只要前一天不比赛就可以，状态转移方程为$f[i][last]=f[i+1][1]$；此时，如果$a[i]=3$健身房才会开放，才有运动的可能，状态转移方程为$f[i][last]=f[i+1][2]$。
3. 如果$a[i]$是偶数，比赛不进行，只要$a[i]=2$且前一天没有在运动（即$last \neq 2$），就可以运动，状态转移方程为$f[i][last]=f[i+1][2]$。

以上几种情况选最小的转移即可，最终的答案就是$f[1][0]$。

复杂度分析

时间复杂度

状态数量为$3n$，单次转移的时间复杂度为$O(1)$，因此算法整体的时间复杂度为$O(n)$。

空间复杂度

空间瓶颈为DP数组$f$，规模是$3n$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int a[N], f[N][3], n;

int dfs(int i, int last) {
    if(i > n) return 0;
    int &v = f[i][last];
    if(v != -1) return v;
    int cnt = 1 + dfs(i + 1, 0);      // 休息
    if(a[i]&1) {
        // 可以比赛
        if(a[i] == 1) {
            // 没法运动
            if(last != 1) cnt = min(cnt, dfs(i + 1, 1));    // 比赛
        }else {
            if(last != 1) cnt = min(cnt, dfs(i + 1, 1));    // 比赛
            if(last != 2) cnt = min(cnt, dfs(i + 1, 2));    // 运动
        }
    }else {
        // 不能比赛
        if(a[i] == 2 && last != 2) cnt = min(cnt, dfs(i + 1, 2));    // 运动
    }
    return v = cnt;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, 0));
    return 0;
}