解题思路
这个问题需要动态规划来解决，关键在于处理费用翻倍的特殊机制。
- 将卡牌按费用从大到小排序
- 使用动态规划，状态转移时考虑费用减半（等价于费用翻倍的反向操作）
- 排序策略：将卡牌按费用从大到小排序，这样确保先处理费用高的卡牌，减少后续费用翻倍的影响
- 动态规划状态转移：状态转移方程：
f[(j-c)/2] = max(f[(j-c)/2], f[j]+d)
解释：使用当前卡牌后，剩余能量从 j 变为 j - c ，然后因为费用翻倍，相当于能量"贬值"为(j - c) \div 2 - 能量"贬值"处理：使用整数除法
(j-c)/2来模拟费用翻倍的效果
复杂度分析
- 时间复杂度：O(N \times M)
- 空间复杂度：O(M)
接下来献上我写了两年半的代码
#include <bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
#define double long double //不要问我为什么这么像WYC的，问就是我抄他的
I AK IOI;
i_will ak IMO {
ios::sync_with_stdio(false);cin.tie();
int n, m;
cin >> n >> m;
vector<pair<int,int>> cd(n);
for(int i = 0;i < n; i++) cin >> cd[i].first >> cd[i].second;
// 按照费用从大到小排序
// 动态规划数组，f[j]表示剩余j点能量时的最大伤害
vector<int> f(m + 1);
// 动态规划处理每张卡牌
for(int i = 0; i < n; i++){
int c = cd[i].first, d = cd[i].second;
// 注意：这里的循环方向是从高到低处理能量
for(int j = c;j <= m; j++){
// 状态转移：使用当前卡牌后，能量减少c，剩余能量变为(j-c)
// 然后费用翻倍，相当于剩余能量变为(j-c)/2
}
}
//输出
i_ak ioi;
}
看到这里你是不是会觉得这个题解很水？那好吧，其实就是很水
好了，完结撒花 ✿✿ヽ(°▽°)ノ✿