[loj 3182]「CEOI2018」云计算

题目链接

https://loj.ac/problem/3182

题解

乍一看购买电脑和接单是两个截然不同的操作，但事实上这两个操作可以同一为同一种操作。

购买电脑可以认为是消耗一些钱（即收益为负）购买一定数量的核心；而接单则是消耗一些核心获得一定收益。最终的目标是在核心数非负的前提下，使得收益最大化。

这显然是一个背包的模型。

问题在于怎样确保接单消耗的核心都符合频率要求呢？我们可以将按频率降序进行排序，这样对第 \(i\) 个物品进行转移的时候，就只会用到频率不低于当前物品要求的核心了。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
 int c,f,v,type;
}a[4005];
long long f[100005];
bool cmp(const node&a,const node&b)
{
 return a.f>b.f||(a.f==b.f&&a.type<b.type);
}
int main()
{
 int n,m;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i].c>>a[i].f>>a[i].v;
  a[i].type=0;
 }
 cin>>m;
 for(int i=n+1;i<=n+m;i++)
 {
  cin>>a[i].c>>a[i].f>>a[i].v;
  a[i].type=1;
 }
 sort(a+1,a+n+m+1,cmp);
 int sc=0;
 memset(f,191,sizeof(f));
 f[0]=0;
 for(int i=1;i<=n+m;i++)
 {
  int t=a[i].type,c=a[i].c,v=a[i].v;
  if(!t)
  {
   for(int j=sc;j>=0;j--)
    f[j+c]=max(f[j+c],f[j]-v);
   sc+=c;
  }
  else
  {
   for(int j=c;j<=sc;j++)
    f[j-c]=max(f[j-c],f[j]+v);
  }
 }
 long long ans=0;
 for(int i=0;i<=sc;i++)
  ans=max(ans,f[i]);
 cout<<ans<<endl;
 return 0;
}