目录
显示
题目链接
题解
馒头的装载顺序是任意的,因此肯定先把价值高的馒头装到盒子里卖。
将所有馒头按价格降序排序后作一遍前缀和就可以知道卖出 \(i\) 个馒头的最大收益 \(f_i\)。
因此我们的目标是在卖出去的馒头数量一定时,买盒子的开支最小。
设 \(g_i\) 为装下 \(i\) 个馒头的最小开支。这个可以用背包来解决。
最后所有 \(f_i-g_i\) 的最大值即为最大收益。
#include <cstring> #include <iostream> #include <algorithm> using namespace std; int f[10005],g[10005],p[10005]; bool cmp(int x,int y) { return x>y; } int main() { int m,n; cin>>m>>n; for(int i=1;i<=m;i++) cin>>p[i]; sort(p+1,p+m+1,cmp); for(int i=1;i<=m;i++) f[i]=f[i-1]+p[i]; memset(g,63,sizeof(g)); g[0]=0; for(int i=1;i<=n;i++) { int c,e; cin>>c>>e; for(int j=m;j>=0;j--) g[j]=min(g[j],g[max(j-c,0)]+e); } int ans=0; for(int i=0;i<=m;i++) ans=max(ans,f[i]-g[i]); cout<<ans<<endl; return 0; }