题目传送门
思路
Lemma. 按照 升序购买一定最优。
Proof. 设先后购买的为 其中 。此时的答案为 。假设不这样买,那么答案为 ,证毕。
然后就可以将 排个序,假设 表示买 的 物品,恶魔使用了 次 magic 的收益。
那么有:
但是,这样有个问题,就是你不知道前面的哪些 是有贡献的,所以要将 按倒序排序,再这样跑动态规划。
时间复杂度:
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e5 + 10;
#define V first
#define C second
long long T, Dp[MAXN][15], N, K;
pair<long long, long long> Num[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--) {
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> Num[i].V >> Num[i].C;
}
sort(Num + 1, Num + 1 + N, [](auto a, auto b) {
return a.V > b.V;
});
for (int i = 1; i <= N; i++) {
Dp[i][0] = max(Dp[i - 1][0], Num[i].V - Num[i].C);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
Dp[i][j] = max(Dp[i - 1][j], min(Dp[i - 1][j - 1] - Num[i].C, Num[i].V - Num[i].C));
}
}
cout << Dp[N][K] << endl;
}
return 0;
}