洛谷[USACO22DEC] Bribing Friends G

题目大意

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

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

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

题解

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

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

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

时间复杂度为$O(n(a+b))$。

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