自动搬运

查看原文

来自洛谷，原作者为

	Mikefeng **

搬运于2025-08-24 22:43:35，当前版本为作者最后更新于2022-12-25 12:44:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[USACO22DEC] Bribing Friends G

题目描述

Bessie 想要观看纪录片：奶牛基因组学，但她不想一个人去。不幸的是，她的朋友们没有足够的热情和她一起去！于是，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂武器库中有两种工具：哞尼和冰激凌甜筒。

Bessie 有 $N(1 \le N \le 2000)$ 个朋友。然而，并非所有的朋友都是生而平等的！朋友 $i$ 有受欢迎度 $P_i(1 \le P_i \le 2000)$，Bessie 想最大化陪她的朋友们的受欢迎度之和。朋友 $i$ 只有当 Bessie 给了她 $C_i(1 \le C_i \le 2000)$ 哞尼才愿意陪她。如果 Bessie 给她 $X_i(1 \le X_i \le 2000)$ 个冰激凌甜筒，她还可以给 Bessie $1$ 哞尼的折扣。Bessie 可以从朋友那里得到任意整数数量的折扣，只要这些折扣不会使得朋友倒给她哞尼。

Bessie 有 $A$ 哞尼和 $B$ 个冰激凌甜筒可供使用（$0 \le A,B \le 2000$）。请帮助她求出如果她以最优方案花费她的哞尼和冰激凌甜筒，她可以达到的最大受欢迎度之和。

做法

既然每个朋友每次都只给 $1$ 元钱的折扣，那我只要给要冰激凌最少的那个不就行了。

很可惜，并不行。就像捆绑销售，朋友只是给 Bessie 折扣，而不是直接给她钱，所以给要冰激凌最少的那个不一定是最优的。

但这为我们打开了一个思路：假设我们已经确定了最后要选哪几位朋友，那么优先给需要冰激凌最少的那位是最划算的。

所以我们先将朋友按 $X_i$ 升序排序，然后倒着做一遍01背包，就可以知道如果现在有 $a$ 个哞尼，从后往前找到第 $i$ 个朋友，最大的受欢迎度是多少。

然后再从后往前进行一次dp，枚举有 $b$ 个冰激凌，最大的受欢迎度是多少。

假设 $b$ 个冰激凌完全能收买这个朋友，那么我们还剩 $b'$ 个冰激凌继续去收买先前枚举过的朋友。假设 $b$ 个冰激凌不能完全收买这个朋友，那么之前枚举过的朋友也一定不能再用冰激凌收买，这时就利用第一次的dp，得到最大的受欢迎度是多少。

代码

不太理解的部分可以看代码。

const ll N=205;
const ll M=2005;
const ll inf=0x3f3f3f3f;
ll n,m,k,ans;
struct node{
	ll a,c,x;
}a[M];
ll dp[M][M],f[M][M];
inline bool cmp(node a,node b){
	return a.x<b.x;
}
inline void pre_solve(){
	UF(i,n,1){
		F(j,0,m) dp[i][j]=dp[i+1][j];
		F(j,a[i].c,m) dp[i][j]=max(dp[i][j],dp[i+1][j-a[i].c]+a[i].a);
	}
}
int main(){
	n=read();m=read();k=read();
	F(i,1,n) a[i].a=read(),a[i].c=read(),a[i].x=read();
	sort(a+1,a+n+1,cmp);
	pre_solve();
	UF(i,n,1){
		F(j,0,k){
			f[i][j]=f[i+1][j];
			ll num=min(a[i].c,j/a[i].x);
			ll lst=j-num*a[i].x;
			if(num==a[i].c) f[i][j]=max(f[i][j],f[i+1][lst]+a[i].a);
			else f[i][j]=max(f[i][j],dp[i+1][m-(a[i].c-num)]+a[i].a);
			ans=max(ans,f[i][j]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}