1 条题解
-
0
状态定义:
:第 天看书时,前 天的最少看电视天数。
:第 天打球时,前 天的最少看电视天数。
:第 天看电视时,前 天的最少看电视天数。
状态转移:
如果第 天看电视,前一天可以是任何活动状态。
如果第 天看书,前一天不能是看书。
如果第 天打球,前一天不能是打球。
初始化:
第 天(初始状态)的看电视天数为 ,看书和打球的天数为 ∞(表示不可行)。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> PII; #define x first #define y second const int N = 2e5 + 10, M = 30; int a[N], b[N], c[N]; // 看书,打球,电视 int n; void solve() { int n; cin >> n; for(int i = 1; i <= n; i ++) a[i] = b[i] = c[i] = 1e9; for(int i = 1; i <= n; i ++) { int x; cin >> x; if(x == 1 || x == 3) b[i] = min(c[i - 1], a[i - 1]); if(x == 2 || x == 3) a[i] = min(b[i - 1], c[i - 1]); c[i] = min({a[i - 1], b[i - 1], c[i - 1]}) + 1; } cout << min({a[n], b[n], c[n]}); } int main() { int t = 1; // cin >> t; while(t --) solve(); }
- 1
信息
- ID
- 496
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 3
- 上传者