题目传送门

题目传送门

思路

Lemma. 按照 viv_i 升序购买一定最优。

Proof. 设先后购买的为 (v1,c1),(v2,c2)(v_1,c_1),(v_2,c_2) 其中 v1v2v_1 \le v2。此时的答案为 min(v1c1,v2c1c2)\min(v_1 - c_1, v_2 - c_1 - c_2)。假设不这样买,那么答案为 min(v2c2,v1c1c2)=v1c1c2min(v1c1,v2c1c2)\min(v_2 - c_2, v_1 - c_1 - c_2) = v_1 - c_1 - c_2 \le \min(v_1 - c_1, v_2 - c_1 - c_2),证毕。

然后就可以将 viv_i 排个序,假设 fi,jf_{i,j} 表示买 1i1 \sim i 的 物品,恶魔使用了 jj 次 magic 的收益。

那么有:

fi,j=max(fi1,j,min(fi1,j1ci,vici))f_{i,j} = \max(f_{i - 1,j},\min(f_{i-1,j-1}-c_i,v_i-c_i))

但是,这样有个问题,就是你不知道前面的哪些 cic_i 是有贡献的,所以要将 viv_i 按倒序排序,再这样跑动态规划。

时间复杂度:Θ(nk)\Theta(nk)

代码

#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;
}