bzoj5441: [Ceoi2018]Cloud computing
2024-08-26 13:45:27
跟着大佬做题。。
这题也是有够神仙了。观察一下性质,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 ;
}
最新文章
- Java基础知识点3:集合类
- 王爽<;<;汇编语言>;>; 实验十四
- Eclipse JAVA项目的 目录结构 和 导入
- Hadoop笔记系列 一 用Hadoop进行分布式数据处理(1)
- 稻壳图文模块调不出html代码
- 【hibernate 报错】No serializer found for class org.hibernate.proxy.pojo.javassist.JavassistLazyInitializer 【get和load的区别】
- ArcEngine编写WebService
- D3.js 比例尺的使用
- HTML第五天学习笔记
- JVM剖析
- Android onActivityResult 设置requestCode 返回的code不对
- Javascript 精髓整理篇之三(数组篇)postby:http://zhutty.cnblogs.com
- Android 环境变量配置(Mac)
- JSON反序列化实体类
- OSChinaclient源代码学习(1)--Android与Server的交互
- 抓包分析、多线程爬虫及xpath学习
- oracle数据库查询语句case的用法
- spring boot报Unsupported Media Type Content type &#39;*/*;charset=UTF-8&#39; not supported
- 高级编程T-SQL函数
- HDMI EDID 处理过程
热门文章
- 《Java编程的逻辑》第四部分 文件
- html5——文本阴影
- JS——动态添加事件和移除事件(有待补充...)
- jdbc 使用谨记
- 【译】x86程序员手册21-6.3.5为操作系统保留的指令
- 如何设置“用eclipse开发时自动在顶端产生import”?
- Node.js 命令行程序开发教程 ---------http://www.ruanyifeng.com/blog/2015/05/command-line-with-node.html
- Servlet+JSP(三):第一个Web程序
- BZOJ 1941: [Sdoi2010]Hide and Seek KDtree + 估价函数
- java基本类型和包装类型的区别以及object的公共方法