当前位置:网站首页>POJ2392 SpaceElevator [DP]
POJ2392 SpaceElevator [DP]
2022-07-07 21:51:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题目大意:有一头奶牛要上太空,他有非常多种石头,每种石头的高度是hi,可是不能放到ai之上的高度。而且这样的石头有ci个 将这些石头叠加起来。问可以达到的最高高度。 解题思路:首先对数据进行升序排序。这样才是一个标准的多重背包的问题 为什么要排序? 由于仅仅有这样才干得到最优解,假设一開始就是高的在前面,那么后面有低的却不能选到,就直接选高的去了。这样是不能达到最优解的 使f[i]的状态标记。能否够达到这个高度 这样可以达到取f[i]中i的最大值就可以。
这里要注意max赋初值的时候要赋值为0。不能为-1。由于答案有可能为0
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int type;
int f[44444],usr[44444];
struct Block
{
int h,a,c;
}block[555];
bool cmp(Block a,Block b)
{
return a.a<b.a;
}
int main()
{
scanf("%d",&type);
for(int i=1;i<=type;i++)
{
scanf("%d%d%d",&block[i].h,&block[i].a,&block[i].c);
}
sort(block+1,block+1+type,cmp);
int maxn=0;
f[0]=1;
for(int t=1;t<=type;t++)
{
memset(usr,0,sizeof(usr));
for(int h=block[t].h;h<=block[t].a;h++)
{
if(!f[h] && f[h-block[t].h] && usr[h-block[t].h]+1<=block[t].c)
{
usr[h]=usr[h-block[t].h]+1;
f[h]=1;
maxn=max(h,maxn);
}
}
}
printf("%d\n",maxn);
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116214.html原文链接:https://javaforall.cn
边栏推荐
- STL标准模板库(Standard Template Library)一周学习总结
- kubernetes的简单化数据存储StorageClass(建立和删除以及初步使用)
- Wechat forum exchange applet system graduation design (2) applet function
- 七月第一周
- 深入理解Mysql锁与事务隔离级别
- FreeLink开源呼叫中心设计思想
- 微信论坛交流小程序系统毕业设计毕设(8)毕业设计论文模板
- UE4_UE5结合罗技手柄(F710)使用记录
- Count the top 10 films at the box office and save them in another file
- Adults have only one main job, but they have to pay a price. I was persuaded to step back by personnel, and I cried all night
猜你喜欢
云原生正在吞噬一切,开发者该如何应对?
在软件工程领域,搞科研的这十年!
微信论坛交流小程序系统毕业设计毕设(8)毕业设计论文模板
Wechat forum exchange applet system graduation design (2) applet function
Vulnerability recurrence ----- 49. Apache airflow authentication bypass (cve-2020-17526)
UE4_UE5结合罗技手柄(F710)使用记录
高级程序员必知必会,一文详解MySQL主从同步原理,推荐收藏
[microservices SCG] gateway integration Sentinel
Unity3D学习笔记6——GPU实例化(1)
深入理解Mysql锁与事务隔离级别
随机推荐
Ros2 topic (03): the difference between ros1 and ros2 [01]
网络安全-beef
微信论坛交流小程序系统毕业设计毕设(4)开题报告
Network security - phishing
LDO穩壓芯片-內部框圖及選型參數
PCI-Express接口的PCB布线规则
云原生数据仓库AnalyticDB MySQL版用户手册
Network security sqlmap and DVWA explosion
Dynamics 365 查找字段过滤
网络安全-CSRF
leetcode-520. Detect capital letters -js
Unity3D学习笔记4——创建Mesh高级接口
智慧社區和智慧城市之間有什麼异同
Network security -beef
三问TDM
Quelles sont les similitudes et les différences entre les communautés intelligentes et les villes intelligentes?
13、 System optimization
js 获取对象的key和value
Conversion between commonsmultipartfile and file
Dynamic agent explanation (July 16, 2020)