[USACO22DEC] Bribing Friends G-Toy模板网

这篇具有很好参考价值的文章主要介绍了[USACO22DEC] Bribing Friends G。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

洛谷[USACO22DEC] Bribing Friends G

题目大意

小 $B$ 有 $n$ 个朋友，每个朋友有一个受欢迎度 $p_i$ 。小 $B$ 想邀请部分朋友和他去看电影，且想要最大化这些朋友的受欢迎程度之和。对于朋友 $i$ ，只有当小 $B$ 给他 $c_i$ 元钱，他才会答应去。如果小 $B$ 给他 $x_i$ 个冰激凌，他还可以给小 $B$ 一元的折扣。小 $B$ 可以从朋友那里得到任意整数数量的折扣，只要不是这些朋友倒贴他。

小 $B$ 有 $a$ 元钱和 $b$ 个冰激凌，求他在采用最佳策略的情况下，可以达到的最大的受欢迎程度之和。

$1\leq n\leq 2000,0\leq a,b\leq 2000$

题解

将朋友根据 $x_i$ 从小到大排序，那么显然冰激凌对前面的朋友用，钱对后面的朋友用才更优。而且，既用了冰激凌又用了钱的朋友最多只有一个，因为如果有两个，则将后一个的冰激凌用在前一个，前一个的钱用在后一个，这样能使要用的冰激凌数量更少。

用两个背包来处理。设 $f_{i,j}$ 表示前 $i$ 个朋友中花费 $j$ 个冰激凌能邀请到朋友的最大欢迎度， $g_{i,j}$ 表示第 $i$ 个朋友到第 $n$ 个朋友中花费 $j$ 元钱能邀请到朋友的最大欢迎度。那么

如果没有既用了冰激凌又用了钱的朋友，则枚举最后一个只用了冰激凌的朋友，更新答案
如果有既用了冰激凌又用了钱的朋友，则枚举这个朋友，并枚举这个朋友所花费的冰激凌和钱，更新答案

时间复杂度为 $O (n (a + b))$ 。文章来源地址https://www.toymoban.com/news/detail-554371.html

code

#include<bits/stdc++.h>
using namespace std;
int n,v1,v2,ans,f[2005][2005],g[2005][2005];
struct node{
	int p,c,x;
}w[2005];
bool cmp(node ax,node bx){
	return ax.x<bx.x;
}
int main()
{
	scanf("%d%d%d",&n,&v1,&v2);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&w[i].p,&w[i].c,&w[i].x);
	}
	sort(w+1,w+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v2;j++){
			f[i][j]=f[i-1][j];
			if(j>=w[i].c*w[i].x)
			f[i][j]=max(f[i][j],f[i-1][j-w[i].c*w[i].x]+w[i].p);
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=0;j<=v1;j++){
			g[i][j]=g[i+1][j];
			if(j>=w[i].c) g[i][j]=max(g[i][j],g[i+1][j-w[i].c]+w[i].p);
		}
	}
	ans=g[1][v1];
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i][v2]+g[i+1][v1]);
		for(int j=v2,k=0;j>=0&&k<=w[i].c;j-=w[i].x,k++){
			if(v1-w[i].c+k>=0)
			ans=max(ans,f[i-1][j]+g[i+1][v1-w[i].c+k]+w[i].p);
		}
	}
	printf("%d",ans);
	return 0;
}