传送门。
题意
有 \(n\) 个物品,\(m\) 个背包。第 \(i\) 个物品的价值是 \(P_i\),第 \(j\) 个背包可以装 \(C_i\) 个物品,但会消耗 \(E_i\) 的价值。
背包不能重复买,问最多可以获得多少价值。
分析
首先一个简单的贪心,我们在购买背包后塞入物品,一定时从大往小塞,也就是说,我们可以先对物品从大到小排序并求前缀和。
其次,我们对购买背包进行求最小,显然,使用 01 背包即可,为了防止我们的可以塞的容量大于我们选取的物品,将数组后缀取最小即可。
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 2e4+5;
inline int read() {
int x;
scanf("%d",&x);
return x;
}
int n, m,a[N],qzh[N],f[N];
signed main() {
// freopen("bread.in","r",stdin);
// freopen("bread.out","w",stdout);
n=read(),m=read();
for(int i=1; i<=n; ++i) a[i]=read();
sort(a+1,a+n+1,greater<int >());
for(int i=1; i<=n; ++i) qzh[i]=qzh[i-1]+a[i];
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1; i<=m; ++i) {
int cnt=read(),val=read();
for(int j=N-1; j>=cnt; --j) f[j]=min(f[j],f[j-cnt]+val);
}
for(int i=N-2; i; --i) f[i]=min(f[i],f[i+1]);
int ans=0;
for(int i=1; i<=n; ++i) ans=max(ans,qzh[i]-f[i]);
cout<<ans<<endl;
return 0;
}
标签:背包,int,题解,read,IOI,2014,物品,JOI
From: https://www.cnblogs.com/djh0314/p/17966152