自动搬运

查看原文

来自洛谷，原作者为

	qvzeyang 大专小子

搬运于2025-08-24 22:03:23，当前版本为作者最后更新于2022-01-23 17:55:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，需要先得出一个结论，购买物品需要依照一个贪心的策略，购买的顺序需要按照 $v_i$ 升序，证明如下。

设 $v_1\le v_2$，则依照升序的代价即 $\min(v_1-c_1,v_2-c_1-c_2)$，而如果交换两个物品，按照降序购买，代价则为 $\min(v_2-c_2,v_1-c_1-c_2)$，由于 $v_1\le v_2$，所以易得 $v_1-c_1-c_2 \le \min(v_1-c_1,v_2-c_1-c_2)$。证得，购买顺序应按照 $v_i$ 升序进行。

之后便是 DP 的转移，可以发现，从最后一件商品向前转移更为简单，为了下标的方便，这里将 $v_i$ 降序排列从 $1$ 向 $n$ 枚举转移。

设dp[i][j]，表示从 $1$ 开始选到了 $i$，一共用了 $j$ 次魔法。易得使用 0 次魔法时dp[i][0]=max(dp[i-1][0],v[i]-c[i])。

进行转移，可得dp[i][j]=max(dp[i-1][j],min(v[i]-c[i],dp[i-1][j-1]-c[i])。
分析这个转移方程，dp[i-1][j]意味着并不选 $i$ 这件物品，min(v[i]-c[i],dp[i-1][j-1])表示小恶魔选取的更优秀的选项，即对于购买者更小的获利，其分别表示将 $i$ 这件物品设为购买的最后一件、对购买的 $i$ 物品使用魔法。最终答案为dp[n][k]。代码如下。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
	#define int long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
int dp[200000][10],n,k;
struct node{int value,cost;}a[1000000];
int cmp(node x,node y){return x.value>y.value;}
signed main(){
	int T=read();
	while(T--){
		n=read(),k=read();
		for(int i=1;i<=n;i++)a[i].value=read(),a[i].cost=read();
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<=n;i++)dp[i][0]=max(dp[i-1][0],a[i].value-a[i].cost);
		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]-a[i].cost,a[i].value-a[i].cost));
			}
		}
		printf("%lld\n",dp[n][k]);
	} 
	return 0;
}