当前位置:网站首页>POJ2392 SpaceElevator [DP]
POJ2392 SpaceElevator [DP]
2022-07-07 23:23:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The main idea of the topic : There is a cow going into space , He has many kinds of stones , The height of each stone is hi, But you can't put it ai Height above . And such stones have ci individual Stack these stones . Ask the highest height you can reach . Their thinking : First, sort the data in ascending order . This is a standard multiple backpack problem Why order ? Because only in this way can we get the optimal solution , Suppose the high one is in front at the beginning , Then there are low ones in the back, but you can't choose , Just choose the higher one . In this way, the optimal solution cannot be reached send f[i] The status flag of . Can it reach this height In this way, we can get f[i] in i The maximum value of .
Pay attention here max When assigning the initial value, it should be assigned as 0. Not for -1. Because the answer may be 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;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116214.html Link to the original text :https://javaforall.cn
边栏推荐
- Wechat forum exchange applet system graduation design completion (7) Interim inspection report
- Matlab 信号处理【问答随笔·2】
- ./ setup. Insufficient sh permission
- V-for traversal object
- Gee (IV): calculate the correlation between two variables (images) and draw a scatter diagram
- Matlab-SEIR传染病模型预测
- Install Fedora under RedHat
- HDU 4747 Mex「建议收藏」
- 智慧社區和智慧城市之間有什麼异同
- 14、 Two methods of database export and import
猜你喜欢
Wechat forum exchange applet system graduation design completion (6) opening defense ppt
Wechat forum exchange applet system graduation design (5) assignment
Unity3d learning notes 5 - create sub mesh
Oracle-数据库的备份与恢复
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
UE4_UE5蓝图command节点的使用(开启关闭屏幕响应-log-发布全屏显示)
Binary tree
伸展树(一) - 图文解析与C语言实现
In the field of software engineering, we have been doing scientific research for ten years!
ArcGIS: field assignment_ The attribute table field calculator assigns values to fields based on conditions
随机推荐
Network security -beef
re1攻防世界逆向
深入理解Mysql锁与事务隔离级别
Spark 离线开发框架设计与实现
Wechat forum exchange applet system graduation design (2) applet function
位运算(Bit Operation)
解决:信息中插入avi格式的视频时,提示“unsupported video format”
Dynamic agent explanation (July 16, 2020)
Specific method example of V20 frequency converter manual automatic switching (local remote switching)
UE4_UE5结合罗技手柄(F710)使用记录
Count the top 10 films at the box office and save them in another file
十四、数据库的导出和导入的两种方法
PHP uses Alibaba cloud storage
LeeCode -- 6. Z 字形变换
The 19th Zhejiang Provincial Collegiate Programming Contest 2022浙江省赛 F.EasyFix 主席树
Byte hexadecimal binary understanding
FPGA基础篇目录
Bit operation
V-for traversal object
Network security - Eternal Blue