首页 > 其他分享 >P1156 垃圾陷阱

P1156 垃圾陷阱

时间:2024-03-03 23:44:42浏览次数:26  
标签:能撑 int 高度 垃圾 陷阱 P1156 unit

原题链接

题解

太妙了
如果能出去,那么出去的时间一定为让我出去的那个垃圾掉落的时间,且在此之前我所在的高度能撑到我垃圾掉落
如果出不去,我肯定一直呆在井底不动

所以我们可以以高度为变量 设每个高度能撑到的最久的时间
而每个垃圾在拿到的一瞬间要么吃要么搭,所以我们穷举,两个都要,如果搭,那么搭上去的高度更新,如果吃,现在的高度更新
如果从高度高到低遍历是不会有重复的计算
避免二的次方级别运算的核心是对达到的每个高度取舍,取能坚持最久的那套方案

code

#include<bits/stdc++.h>
using namespace std;
struct unit
{
    int t,heal,h;
}r[105];

bool cmp(unit a,unit b)
{
    return a.t<b.t;
}

int last[105]={0};//代表当前高度最多能撑到什么时候
int main()
{
    int height,n;
    cin>>height>>n;
    for(int i=1;i<=n;i++) cin>>r[i].t>>r[i].heal>>r[i].h;

    sort(r+1,r+n+1,cmp);
    last[0]=10;
    for(int i=1;i<=n;i++)
    {
        for(int h=height;h>=0;h--)
        {
            if(last[h]>=r[i].t)//如果能撑到垃圾到来
            {
                if(h+r[i].h>=height)//瞬间开溜
                {
                    cout<<r[i].t;
                    return 0;
                }
                last[h+r[i].h]=max(last[h+r[i].h],last[h]);//每个垃圾都有两个去处
                last[h]+=r[i].heal;
            }
        }
    }

    cout<<last[0];
    return 0;
}

标签:能撑,int,高度,垃圾,陷阱,P1156,unit
From: https://www.cnblogs.com/pure4knowledge/p/18051006

相关文章

  • AI智能分析网关V4智慧环保/智慧垃圾站视频智能分析与监控方案
    一、背景介绍随着城市化进程的加速,垃圾处理问题日益受到人们的关注,传统的垃圾站管理方式已经无法满足现代社会的需求。针对当前垃圾站的监管需求,TSINGSEE青犀可基于旗下视频智能检测AI智能分析网关V4与安防监控视频综合管理系统EasyCVR平台,打造智慧垃圾站视频监控与智能分析方案......
  • 团队管理中的隐形陷阱:管理者易忽视的问题及应对策略
    团队管理中的隐形陷阱:管理者易忽视的问题及应对策略在团队管理的过程中,许多管理者都致力于建立高效、协作的团队,但往往在实践中会忽视一些关键要素。这些看似细微的问题,却可能对团队的整体效能产生深远影响。本文将探讨团队管理者在管理过程中容易忽视的几个问题。1.缺乏明确的......
  • 内存与垃圾回收篇之(四)程序计数器
    程序计数器(PC寄存器)1.PCRegister介绍​ JVM中的程序计数寄存器(ProgramCounterRegister)中,Register的命名源于CPU的寄存器,寄存器存储指令相关的现场信息。CPU只有把数据装载到寄存器才能够运行。​ 这里,并非是广义上所指的物理寄存器,或许将其翻译为PC计数器(或指令计数......
  • 内存与垃圾回收篇之(三)运行时数据区概述及线程
    运行时数据区概述及线程1.概述经过类加载器子系统之后,方法区中就保存了运行时类本身。​ 内存是非常重要的系统资源,是硬盘和CPU的中间仓库及桥梁,承载着操作系统和应用程序的实时运行。JVM内存布局规定了Java在运行过程中内存申请、分配、管理的策略,保证了JVM的高效稳定运行。......
  • 内存与垃圾回收篇之(二)类加载器子系统
    类加载器子系统1.内存结构概述如果自己手写一个Java虚拟机的话,主要考虑哪些结构呢?类加载器和执行引擎2.类的加载器及类加载过程2.1类加载器子系统的作用类加载器子系统负责从文件系统或者网络中加载Class文件,class文件在文件开头有特定的文件标识。ClassLoader只负责c......
  • 内存与垃圾回收篇之(一)JVM与Java体系结构
    JVM与Java体系结构1.前言JVM拥有当前最前沿、最成熟的垃圾回收算法JIT:即时编译器AOT:提前编译器JVM:代码托管技术拓展:前端编译器:负责把Java文件编译成Class文件,如Sun的Javac;后端运行期编译器(JIT编译器):负责把Class文件的字节码转换成机器码,如HotSpot的C1,C2编译器;静态提前......
  • 垃圾分类新篇章:大屏引领,共筑环保未来
    在当下社会,垃圾分类已成为我们日常生活中不可或缺的一部分。随着环保意识的逐渐增强,如何高效、准确地进行垃圾分类成为了摆在我们面前的重要课题。而垃圾分类管理大屏作为一种创新的管理工具,正逐渐走进我们的生活,助力我们共同构建绿色、和谐的居住环境。 垃圾分类管理大屏,集数......
  • 怎样建设供应商文件分发平台?这三点陷阱需注意
    供应商在市场经济中是不可或缺的角色,供应商作为重要的环节,串联起从商品生产到消费者的链路,而供应商特殊的点在于供应商并不能单独存在,相反它与上下游关系非常紧密。上游供应商是指向供应商提供原材料、零部件或其他支持的企业或组织。上游供应商通常负责生产或制造商品所需的原......
  • JAVA基础-内存与垃圾回收
    1,运行时数据区1,程序计数器线程私有。生命周期:生命周期与线程同步。作用:它是程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都需要依赖这个计数器来完成。特点:它是一块很小的内存空间,几乎可以忽略不记。也是运行速度最快的存储区域,唯一没有OutofMemory......
  • 垃圾收集2
    1.标记-清除算法算法分为标记和清除两个阶段:首先标记出所有需要回收的对象,在标记完成后,统一回收掉所有被标记的对象,也可以反过来,标记存活的对象,统一回收所有未被标记的对象。标记过程就是对象是否属于垃圾的判定过程。主要缺点有两个:第一个是执行效率不稳定,如果Ja......