题目链接

题解

按照频率排序后转化成背包问题。

代码

#include 
    
     #include 
     
      #include 
      
       int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=2000;const int maxm=50;struct query{  int c,f,v;  bool operator <(const query &other) const  {    if(f==other.f)      {        return v
       
        other.f;  }};long long f[maxn*maxm+10],ans;int n,m,tot;query q[maxn*2+10];int main(){  n=read();  for(int i=1; i<=n; ++i)    {      q[i].c=read();      q[i].f=read();      q[i].v=-read();    }  m=read();  for(int i=1; i<=m; ++i)    {      q[n+i].c=-read();      q[n+i].f=read();      q[n+i].v=read();    }  std::sort(q+1,q+n+m+1);  memset(f,-63,sizeof f);  f[0]=0;  for(int i=1; i<=n+m; ++i)    {      if(q[i].c>0)        {          for(int j=tot; j>=0; --j)            {              f[j+q[i].c]=std::max(f[j+q[i].c],f[j]+q[i].v);            }          tot+=q[i].c;        }      else        {          for(int j=0; j-q[i].c<=tot; ++j)            {              f[j]=std::max(f[j],f[j-q[i].c]+q[i].v);            }        }    }  for(int i=0; i<=tot; ++i)    {      ans=std::max(ans,f[i]);    }  printf("%lld\n",ans);  return 0;}