部分来自 @wylTUN
1.首先考虑状态表示
f[i][j]
表示到第 i 天选择了 j 这个方式来度过这一天最多有几天出去了2.再考虑状态转移
f[i][0]
表示今天休息,那么昨天干什么都行
f[i][1]
表示今天去图书馆,那么昨天可以休息也可以去健身房
f[i][2]
表示今天去健身房,那么昨天可以休息或者去图书馆
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int f[N][3],w[N];
int n;
int main(){
cin >> n;
for(int i = 1;i <= n;i++) cin >> w[i];
for(int i = 1;i <= n;i++){
f[i][0] = max({f[i - 1][0],f[i - 1][1],f[i - 1][2]});//今天休息
//去图书馆
if(w[i] == 1 || w[i] == 3) f[i][1] = max(f[i - 1][1],max(f[i - 1][0],f[i - 1][2]) + 1);
//去健身房
if(w[i] == 2 || w[i] == 3) f[i][2] = max(f[i - 1][2],max(f[i - 1][0],f[i - 1][1]) + 1);
}
int res = 0;
res = max({res,f[n][0],f[n][1],f[n][2]});
cout << n - res << endl;
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], f[N][3];
int main ()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> w[i];
memset(f, -0x3f, sizeof f);
f[0][2] = 0;//默认第0天是休息的
for(int i = 1; i <= n; i ++)//从第一天开始遍历
for(int j = 0; j < 3; j ++)
if(j == 2 || (w[i] >> j & 1))//休息或者今天和昨天的状态不同
for(int k = 0; k < 3; k ++)
if(j == 2 || j != k) //状态可转移
f[i][j] = max(f[i][j], f[i - 1][k] + (j != 2));
cout << n - max({f[n][0], f[n][1], f[n][2]}) << endl;
return 0;
}