官方题解｜万圣糖果

题目解析

动态规划；状态DP

考虑进行状态DP，并从前到后考虑所有礼盒，那么会涉及到 $6$ 种状态。

1. 未使用魔法，礼盒中的糖果数量状态为 $A$。
2. 使用 $1$ 次魔法，礼盒中的糖果状态为 $B$。
3. 使用 $1$ 次魔法，礼盒中的糖果状态为 $A$（即第一次使用魔法的区间结束了）。
4. 使用 $2$ 次魔法，礼盒中的糖果状态为 $C$。（即和第一次使用魔法的区间重合的部分）
5. 使用 $2$ 次魔法，礼盒中的糖果状态为 $B$。（即第和第一次使用魔法的区间不重合的部分）
6. 使用 $2$ 次魔法，礼盒中的糖果状态为 $A$。（即两次使用魔法的区间全部结束）

令 $dp_0, dp_1, \cdots, dp_5$ 分别对应以上 $6$ 种状态下前 $i$ 个礼盒能够拿到的最多的糖果的数量；那么有以下关系转移方式。

令 $dpI$ 为前 $i$ 个礼盒能够拿到的最多的糖果的数量，讨论如何从前 $i - 1$ 个礼盒能够拿到的最多的糖果数量 $dp$ 转移到 $dpI$。

1. $dpI_0 = dp_0 + a_i$
2. $dpI_1 = \max{(dp_0, dp_1)} + b_i$
3. $dpI_2 = \max{(dp_1, dp_2)} + a_i$
4. $dpI_3 = \max{(dp_0, dp_1, dp_3)} + c_i$
5. $dpI_4 = \max{(dp_2, dp_3, dp_4)} + b_i$
6. $dpI_5 = \max{(dp_3, dp_4, dp_5)} + a_i$

最终 $\max{(dp_0, dp_1, \cdots, dp_5)}$ 便是答案。

时间复杂度 $\mathrm{O}(N)$。

AC代码

#include <bits/stdc++.h>
 
using i64 = long long;

constexpr i64 INF = 2e14;

template<class T>
std::istream& operator >> (std::istream &in, std::vector<T> &vec) {
    for (auto &x : vec) in >> x;
    return in;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n; std::cin >> n;
    std::vector<int> a(n), b(n), c(n);
    std::cin >> a >> b >> c;
    std::vector<i64> dp(6, -INF);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        auto dpI = dp;
        dpI[0] = dp[0] + a[i]; // 0A
        dpI[1] = std::max(dp[0], dp[1]) + b[i]; // 1B
        dpI[2] = std::max(dp[1], dp[2]) + a[i]; // 1A
        dpI[3] = std::max({dp[0], dp[1], dp[3]}) + c[i]; // 2c
        dpI[4] = std::max({dp[2], dp[3], dp[4]}) + b[i]; // 2B
        dpI[5] = std::max({dp[3], dp[4], dp[5]}) + a[i]; // 2A
        dp = std::move(dpI);
    }
    std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}