題目敘述

Vasya 每天可以做一件事：運動或打比賽，但每一天運動場可能會開或關、每一天也可能有比賽或沒比賽。 但是 Vasya 不喜歡連續兩天做同一件事情──他寧可休息。 現在給你連續 $n$ 天運動場和比賽的情況，請問 Vasya 至少得休息幾天？

解法

乍看之下這題需要 DP，記錄下第 $i$ 天做哪件事情的時候，到該天為止至少要休息幾天。 但實際上我們可以 greedy 記錄下第 $i$ 天有哪些事情可做都能達到最少天數即可。

參考程式碼

// by tmt514
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
using namespace std;
typedef long long LL;

int n, a[105];
int main(void) {
  scanf("%d", &n);
  for(int i=0;i<n;i++) scanf("%d", &a[i]);
  int last = 0, rest = 0;
  for(int i=0;i<n;i++) {
    if (a[i] == 0) ++rest, last = 0;
    else if (a[i] == 3) last = (last == 3? 3 : 3 - last);
    else if (a[i] == last) ++rest, last = 0;
    else last = a[i];
  }
  printf("%d\n", rest);
  return 0;
}