[loj 2757]「JOI 2014 Final」IOI 馒头

题目链接

https://loj.ac/problem/2757

题解

馒头的装载顺序是任意的，因此肯定先把价值高的馒头装到盒子里卖。

将所有馒头按价格降序排序后作一遍前缀和就可以知道卖出 \(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;
}