1 条题解

  • 0
    @ 2026-11-12 21:40:36

    [C] Vacation(dp_c)题解

    题意简述

    NN 天,每天在 A/B/C 三活动中选一项分别获得 ai,bi,cia_i, b_i, c_i,但相邻两天不能做同一项。求最大收益。

    思路

    状态

    "昨天做了什么"决定了今天不能做什么,于是把活动类型也放进状态:

    • AiA_i:第 ii 天做 A 的最大收益;
    • BiB_i:第 ii 天做 B 的最大收益;
    • CiC_i:第 ii 天做 C 的最大收益。

    转移(第 ii 天做 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}).$$

    初值 A0=B0=C0=0A_0 = B_0 = C_0 = 0(等价于实现时直接令第一天的三个值等于 a1,b1,c1a_1, b_1, c_1)。答案 max⁡(AN,BN,CN)\max(A_N, B_N, C_N)。

    为什么正确

    每天的收益只与"今天选什么、昨天选什么"有关,是典型的"相邻不同"型 DP。状态 (天数, 昨天活动) 覆盖了所有后续决策所需的信息。

    复杂度

    时间 O(N)O(N),空间 O(1)O(1)(滚动)。

    参考代码

    #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;
    }
    

    易错点

    1. 必须同时更新三个变量;若先算 AA 再用新的 AA 算 BB,就允许了"连续两天做 A"。
    2. 答案取三者最大,不是取 ANA_N。
    3. N=1N=1 时答案 max⁡(a1,b1,c1)\max(a_1,b_1,c_1),滚动写法天然正确。

    数据说明

    共 13 组:3 组官方样例;N=1N=1、全相同值、交替极值、N=1000/104N=1000/10^4 随机;N=105N=10^5 随机三组与"a 恒为最大"的构造组,用于检验"相邻不同"约束是否严格实现。

    • 1

    信息

    ID
    12
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者