3259. 超级饮料的最大强化能量

发表于 分类于 阅读次数： Waline： 本文字数： 505 阅读时长 ≈ 2 分钟

考点

  • 状态机DP

思路

一、状态定义（State）

设： \[ f[i][0] = \text{前 } i \text{ 天，且第 } i \text{ 天喝 A 的最大能量} \] 其中：

  • \(i \in [0, n]\)
  • energyDrinkA[i-1] 表示第 \(i\) 天喝 A 的收益
  • energyDrinkB[i-1] 表示第 \(i\) 天喝 B 的收益

二、初值（Initialization）

第 0 天什么都没喝： \[ f[0][0] = 0 \] 对应代码：

1
f[0][0] = f[0][1] = 0;

这一步非常关键，它保证：

  • 第 1 天无论选 A 还是 B 都有合法转移来源
  • 不需要特判第一天

三、状态转移方程（Transition）

第 \(i\) 天（从 1 开始）：

1️⃣ 今天喝 A（状态 0）

要么：

  • 昨天喝 B → 今天切换到 A
  • 昨天也喝 A → 累加 A 的收益

\[ f[i][0] = \max\Big( f[i-1][1],\; f[i-1][0] + energyDrinkA[i-1] \Big) \]

代码：

1
f[i][0] = max(f[i - 1][1], f[i - 1][0] + energyDrinkA[i - 1]);

2️⃣ 今天喝 B（状态 1）

同理： \[ f[i][1] = \max\Big( f[i-1][0],\; f[i-1][1] + energyDrinkB[i-1] \Big) \] 代码：

1
f[i][1] = max(f[i - 1][0], f[i - 1][1] + energyDrinkB[i - 1]);

🔑 本质含义总结

当前选择 昨天来源 是否累加
A B → A 不累加
A A → A 累加 A
B A → B 不累加
B B → B 累加 B

这个 DP 本质是一个“两状态滚动最优切换 + 累加”模型。

四、最终答案（Result）

最后一天可以喝 A 或 B，取最大值： \[ \text{Answer} = \max(f[n][0],\; f[n][1]) \] 对应代码：

1
return max(f[n][1], f[n][0]);

五、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maxEnergyBoost(vector<int>& energyDrinkA,
                             vector<int>& energyDrinkB) {
        long long f[maxn][2], n = energyDrinkA.size();
        f[0][0] = f[0][1] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i][1] = max(f[i - 1][0], f[i - 1][1] + energyDrinkB[i - 1]);
            f[i][0] = max(f[i - 1][1], f[i - 1][0] + energyDrinkA[i - 1]);
        }
        return max(f[n][1], f[n][0]);
    }
};

滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static const int maxn = 1e5 + 5;
    long long maxEnergyBoost(vector<int>& energyDrinkA,
                             vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        long long x = 0, y = 0;
        for (int i = 1; i <= n; ++i) {
            long long tx, ty;
            ty = max(x, y + energyDrinkB[i - 1]);
            tx = max(y, x + energyDrinkA[i - 1]);
            x = tx, y = ty;
        }
        return max(x, y);
    }
};