1 条题解
-
0
[C] Vacation(dp_c)题解
题意简述
天,每天在 A/B/C 三活动中选一项分别获得 ,但相邻两天不能做同一项。求最大收益。
思路
状态
"昨天做了什么"决定了今天不能做什么,于是把活动类型也放进状态:
- :第 天做 A 的最大收益;
- :第 天做 B 的最大收益;
- :第 天做 C 的最大收益。
转移(第 天做 A,前一天只能做 B 或 C):
$$A_i = a_i + \max(B_{i-1}, C_{i-1}),\quad B_i = b_i + \max(A_{i-1}, C_{i-1}),\quad C_i = c_i + \max(A_{i-1}, B_{i-1}).$$初值 (等价于实现时直接令第一天的三个值等于 )。答案 。
为什么正确
每天的收益只与"今天选什么、昨天选什么"有关,是典型的"相邻不同"型 DP。状态 (天数, 昨天活动) 覆盖了所有后续决策所需的信息。
复杂度
时间 ,空间 (滚动)。
参考代码
#include <cstdio> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); long long a, b, c, A = 0, B = 0, C = 0; for (int i = 0; i < n; i++) { scanf("%lld %lld %lld", &a, &b, &c); long long nA = a + max(B, C); long long nB = b + max(A, C); long long nC = c + max(A, B); A = nA; B = nB; C = nC; } printf("%lld\n", max(A, max(B, C))); return 0; }易错点
- 必须同时更新三个变量;若先算 再用新的 算 ,就允许了"连续两天做 A"。
- 答案取三者最大,不是取 。
- 时答案 ,滚动写法天然正确。
数据说明
共 13 组:3 组官方样例;、全相同值、交替极值、 随机; 随机三组与"a 恒为最大"的构造组,用于检验"相邻不同"约束是否严格实现。
- 1
信息
- ID
- 12
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者