喵~ 主人，今天我们来挑战一个关于开宝箱的有趣问题喵！(ฅ'ω'ฅ)
这个问题看起来有点复杂，但别担心，跟着我的思路一步一步来，你很快就能明白啦！
题目大意
我们面前有 n 个宝箱，需要按顺序从 1 到 n 打开它们。第 i 个宝箱里有 a_i 枚金币。
对于每个宝箱，我们有两种钥匙可以选择：
- 好钥匙：需要花费
k枚金币购买。使用后，能获得宝箱里当前所有的金币。 - 坏钥匙：免费。但使用它会产生一个副作用：所有未打开的宝箱（包括正在打开的这一个）里的金币数量都会减半，并向下取整。比如，用坏钥匙开第
i个宝箱，那么a_i, a_{i+1}, \dots, a_n的值都会变成\lfloor \frac{a}{2} \rfloor。
我们一开始没有金币，但是可以负债去买好钥匙。目标是打开所有 n 个宝箱后，拥有的金币数量最多。
解题思路 (动态规划大法好喵！)
这是一个典型的决策问题，对于每个宝箱，我们都要在“花钱保值”（用好钥匙）和“省钱贬值”（用坏钥匙）之间做出选择。当前的选择会影响到未来的收益，这种前后关联的问题，很自然地就想到了动态规划 (DP) 啦，喵~
状态定义
我们从后往前考虑问题会更清晰一些。假设我们正在决定如何开启第 i 个宝箱，我们需要知道什么信息才能做出最优决策呢？
最重要的信息是：在打开第 i 个宝箱之前，我们已经用了多少次坏钥匙。因为用了多少次坏钥匙，直接决定了第 i 个以及之后所有宝箱里金币的数量。
所以，我们可以定义一个 DP 状态： dp[i][j] 表示：在已经使用了 j 次坏钥匙的情况下，从第 i 个宝箱开始，一直到第 n 个宝箱，我们能获得的最大金币数。
我们的最终目标是求 dp[0][0]（从第 0 个箱子开始，用了 0 次坏钥匙能获得的最大收益）。
状态转移
对于 dp[i][j]，我们有两种选择来开第 i 个宝箱：
使用好钥匙：
- 我们需要花费
k金币。 - 第
i个宝箱里的金币因为之前的j次坏钥匙，已经变成了\lfloor \frac{a_i}{2^j} \rfloor。 - 我们从这个箱子获得的收益是
\lfloor \frac{a_i}{2^j} \rfloor - k。 - 因为这次没用坏钥匙，所以对于第
i+1个宝箱，它前面依然是用了j次坏钥匙。 - 总收益 = (当前收益) + (未来收益) = $$(\lfloor \frac{a_i}{2^j} \rfloor - k) + dp[i+1][j]$$。
- 我们需要花费
使用坏钥匙：
- 我们不花钱。
- 第
i个宝箱的金币在之前j次减半的基础上，要再减半一次，所以总共减半了j+1次，变成了\lfloor \frac{a_i}{2^{j+1}} \rfloor。 - 我们从这个箱子获得的收益是
\lfloor \frac{a_i}{2^{j+1}} \rfloor。 - 因为这次用了坏钥匙，所以对于第
i+1个宝箱，它前面就变成了用了j+1次坏钥匙。 - 总收益 = (当前收益) + (未来收益) = `\lfloor \frac{a_i}{2^{j+1}} \rfloor + dp[i+1][j+1]$$。
我们的决策当然是选择收益更大的那个啦！所以状态转移方程就是： dp[i][j] = max( (\lfloor \frac{a_i}{2^j} \rfloor - k) + dp[i+1][j], \lfloor \frac{a_i}{2^{j+1}} \rfloor + dp[i+1][j+1] )
观察与优化
如果直接用这个 DP，状态是 dp[n][n]，复杂度是 O(n^2)，对于 n=10^5 来说太慢了，会超时的喵！
但是，我们来观察一下金币减半这个过程。最大的 a_i 是 10^9。2^{30} \approx 10^9。这意味着，任何一个宝箱里的金币，在经过大约 30 次减半之后，基本上就变成 0 了。用再多的坏钥匙，金币也不会再减少。
所以，我们没必要记录 j 到 n 那么大。我们可以设定一个上限，比如 C = 35。当坏钥匙的使用次数 j 超过 C 时，所有宝箱里的金币都可以看作是 0。
这样，我们的状态 j 只需要从 0 到 C 即可。DP 的复杂度就从 O(n^2) 降到了 O(n \times C)，这就完全可以接受了！
另外，我们注意到计算 dp[i] 的值只依赖于 dp[i+1] 的值。所以我们可以使用滚动数组的思想，把二维 DP 优化成一维，空间复杂度就从 O(n \times C) 降到了 O(C)，非常棒喵！
题解代码
这是用 C++ 实现的思路，喵~
#include <iostream>
#include <vector>
#include <algorithm>
// 为了解决 G. Good Key, Bad Key
void solve() {
int n;
long long k;
std::cin >> n >> k;
std::vector<long long> a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
// C 是一个安全上限，表示坏钥匙能产生非零影响的最大次数。
// a_i 最大是 10^9，log2(10^9) 大约是 29.89。
// 所以经过 30-35 次除以2后，任何 a_i 都会变成 0。
const int C = 35;
// dp[j] 表示在处理当前宝箱 i 之前，已经用了 j 次坏钥匙的情况下，
// 从宝箱 i 到 n 能获得的最大利润。
// 我们从 i = n-1 倒推到 0。
// 这个 `dp` 向量代表的是 i+1 的状态。
std::vector<long long> dp(C + 1, 0);
for (int i = n - 1; i >= 0; --i) {
std::vector<long long> next_dp(C + 1); // 用来存放宝箱 i 的状态
for (int j = 0; j <= C; ++j) {
// 选择1：对宝箱 i 使用好钥匙
// 此时宝箱已被减半 j 次。
// 从这个宝箱获得的利润是 (a[i] / 2^j) - k。
// 未来的利润是 dp[j]（因为坏钥匙数量还是 j）。
// a[i] >> j 等价于 a[i] / (2^j)
long long profit_good = (a[i] >> j) - k + dp[j];
// 选择2：对宝箱 i 使用坏钥匙
// 此时宝箱被减半 j+1 次。
// 从这个宝箱获得的利润是 (a[i] / 2^(j+1))。
// 未来的利润是 dp[j+1]（因为坏钥匙数量变成了 j+1）。
long long profit_bad = (a[i] >> (j + 1));
if (j < C) {
profit_bad += dp[j + 1];
}
// 如果 j == C，再用一个坏钥匙，总数就超过 C 了。
// a[i] >> (C+1) 肯定是 0。
// 未来用 C+1 次坏钥匙的利润也是 0，所以这里的计算是正确的。
next_dp[j] = std::max(profit_good, profit_bad);
}
dp = next_dp; // 更新状态，为计算 i-1 做准备
}
// 循环结束后，dp[0] 就是我们从第0个宝箱开始，用0次坏钥匙的初始状态下，能获得的最大总利润
std::cout << dp[0] << std::endl;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点介绍
这个问题用到了几个很有用的编程竞赛技巧哦！
- 动态规划 (Dynamic Programming)：核心思想是将一个大问题分解成小问题，并储存子问题的解来避免重复计算。这道题从后往前的推导方式（倒序 DP）是 DP 中的常见模式。
- 状态压缩/优化 (State Optimization)：通过观察问题性质，发现 DP 状态的某一维度不需要很大，从而减小状态空间，降低复杂度。这里我们将坏钥匙的次数
j从n优化到常数C，是解题的关键！ - 滚动数组 (Rolling Array)：当 DP 状态转移只依赖于前一个（或前几个）状态时，可以用一个大小固定的数组来滚动存储，大大减少空间开销。
- 位运算 (Bitwise Operations)：代码中的
>>是右移位运算符。x >> j的效果等同于x / (2^j)，但计算速度通常比直接做除法快，是处理与2的幂次相关的乘除法时的小技巧，喵~
希望这篇题解能帮到你喵~ 如果还有不明白的地方，随时可以再来问我哦！(＾• ω •＾)