跟着大佬做题。。

这题也是有够神仙了。观察一下性质,c很小而f是一个限制条件(然而我并不会心态爆炸)

%了一发,就是把电脑和订单一起做背包,订单的c视为负而电脑的v为负,f由大到小排序做背包

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL; struct node{int c,f;LL v;}a[];
bool cmp(node n1,node n2){return n1.f==n2.f?n1.c>n2.c:n1.f>n2.f;}
LL f[];
int main()
{
int n,m;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d%lld",&a[i].c,&a[i].f,&a[i].v);
a[i].v=-a[i].v;
}
scanf("%d",&m);
for(int i=n+;i<=n+m;i++)
{
scanf("%d%d%lld",&a[i].c,&a[i].f,&a[i].v);
a[i].c=-a[i].c;
}
n+=m;
sort(a+,a+n+,cmp); int maxp=;LL lin;
memset(f,-,sizeof(f));f[]=;
lin=f[];
for(int i=;i<=n;i++)
{
if(a[i].c>)
{
for(int j=maxp;j>=;j--)
if(f[j]!=lin)
{
f[j+a[i].c]=max(f[j+a[i].c],f[j]+a[i].v);
if(j+a[i].c>maxp)maxp=j+a[i].c;
}
}
else
{
for(int j=-a[i].c;j<=maxp;j++)
if(f[j]!=lin)
f[j+a[i].c]=max(f[j+a[i].c],f[j]+a[i].v);
}
} LL ans=;
for(int i=;i<=maxp;i++)ans=max(ans,f[i]);
printf("%lld\n",ans);
return ;
}

最新文章

  1. Java基础知识点3:集合类
  2. 王爽&lt;&lt;汇编语言&gt;&gt; 实验十四
  3. Eclipse JAVA项目的 目录结构 和 导入
  4. Hadoop笔记系列 一 用Hadoop进行分布式数据处理(1)
  5. 稻壳图文模块调不出html代码
  6. 【hibernate 报错】No serializer found for class org.hibernate.proxy.pojo.javassist.JavassistLazyInitializer 【get和load的区别】
  7. ArcEngine编写WebService
  8. D3.js 比例尺的使用
  9. HTML第五天学习笔记
  10. JVM剖析
  11. Android onActivityResult 设置requestCode 返回的code不对
  12. Javascript 精髓整理篇之三(数组篇)postby:http://zhutty.cnblogs.com
  13. Android 环境变量配置(Mac)
  14. JSON反序列化实体类
  15. OSChinaclient源代码学习(1)--Android与Server的交互
  16. 抓包分析、多线程爬虫及xpath学习
  17. oracle数据库查询语句case的用法
  18. spring boot报Unsupported Media Type Content type &#39;*/*;charset=UTF-8&#39; not supported
  19. 高级编程T-SQL函数
  20. HDMI EDID 处理过程

热门文章

  1. 《Java编程的逻辑》第四部分 文件
  2. html5——文本阴影
  3. JS——动态添加事件和移除事件(有待补充...)
  4. jdbc 使用谨记
  5. 【译】x86程序员手册21-6.3.5为操作系统保留的指令
  6. 如何设置“用eclipse开发时自动在顶端产生import”?
  7. Node.js 命令行程序开发教程 ---------http://www.ruanyifeng.com/blog/2015/05/command-line-with-node.html
  8. Servlet+JSP(三):第一个Web程序
  9. BZOJ 1941: [Sdoi2010]Hide and Seek KDtree + 估价函数
  10. java基本类型和包装类型的区别以及object的公共方法