首页 > 其他分享 >2021年庐阳区青少年信息学科普日真题- 跳跃(jump)

2021年庐阳区青少年信息学科普日真题- 跳跃(jump)

时间:2024-08-09 23:23:48浏览次数:15  
标签:庐阳区 int sum 日真题 long jump 能量 桃子 dp

题目描述
猴子的正上方,每1米处,都有一个桃子,一共有N个桃子,每个桃子都有其能量值,摘下这个桃子吃下就获得了这个能力值。猴子每跳1米会消耗1个点能量,在能量值允许的下,它可以跳到任何一个可以到达的高度,并且将这个高度及以下高度的桃子摘下吃掉。确保猴子初始的能量一定可以摘下所有的桃子。求该猴子摘下吃掉所有的桃子后,保留最多的能量值

输入格式
第一行 两个整数N和M,表示桃子的数量和猴子的初始能量

第二行,N个非负整数,依次描述从下向上描述各桃子的能量值。

输出格式
一个整数,意义如题所述。

输入输出样例

输入样例1:
3 2
2 2 2


输出样例1:
4

说明
1<=N <=2000000


【解析】
如果这道题你们复制本代码,提示超时的话,请使用scanf/printf进行输入输出,因为本题数据量还是很大的。
1:本题关键字 “最多“,一般几种算法:贪心、二分、搜索、动规。
2:贪心不对,因为就样例,贪心是不成立的。 二分不适合此题;搜索更不行数据太多;只能想动态规划了。

贪心不对,是因为你总想着,能跳多高就跳多高。比如样例,初始能量2,你一下子就跳2个桃子。还不如只跳第一个桃子,不信去试试。
所以本题的策略是:第i个桃子应该是被下面某个最矮的桃子摘下的,因为从最矮的桃子跳上来到第i个桃子,然后直接掉下去,顺手摘掉 i 下面的桃子。
所以状态定义:dp[i] 表示摘完第i个桃子的最大能量值
状态转移方程:dp[i]=max(dp[i], dp[ 0~i-1 ] >= i + sum[i] - sum[j] - i )
dp[ 0~i-1 ] >= i 表示 满足第一次大于 i 的桃子下标

#include <iostream>
using namespace std;
const int N=2000010;
long long  a[N];
long long dp[N];//摘下第i个桃子的能量值 dp[i]
//dp[i]=min(dp[1~i-1])+a[i]-i
long long sum[N];
int main()
{
    int n,m;
    cin>>n>>m;
    dp[0]=m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    int j=0;
    for(int i=1;i<=n;i++){
        while(dp[j]<i){
            j++;
        } 
        dp[i]=max(dp[i],dp[j]+sum[i]-sum[j]-i);
    }
    cout<<dp[n];
    return 0;
}

标签:庐阳区,int,sum,日真题,long,jump,能量,桃子,dp
From: https://blog.csdn.net/ahstunwy/article/details/140921528

相关文章

  • 视频笔记软件JumpVideo技术解析一:Electron案例-调用VLC播放器
              大家好,我是TheGodOfKing,是最强考研学习神器,免费视频笔记应用JumpVideo,可以快速添加截图时间戳,支持所有笔记软件,学习效率MAX!的开发者之一,分享技术的目的是想找到更多志同道合的人,如果有大学生加入,我们还允许他把项目作为毕设(只有一个名额哟)群(689978959),那么今......
  • Python - Creating jump tables using lambda functions
    Wecanplacelambdafunctioninsidelistanddictionaryliterals.Thiswaywecanuselambdaexpressionstocreatejumptables.>>>L=[lambdas:s.strip().lower(),... lambdas:s.strip().upper(),... lambdas:s.lstrip().title(),... lambd......
  • 每日一题- Jump Distance Sum
    https://www.luogu.com.cn/problem/AT_abc351_e*这是我的第一个随笔,请大佬们指正。数学知识:https://oi-wiki.org/geometry/distance/*曼哈顿距离:在二维空间内,两个点之间的曼哈顿距离(Manhattandistance)为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点A(x1,y1),B(x2,......
  • Python反编译失败。 (不支持的操作码:JUMP_IF_NOT_EXC_MATCH)
    我尝试使用“pycdc.exe”反编译使用pycdc.exe失败。因为错误“不支持的操作码:JUMP_IF_NOT_EXC_MATCH”在此处输入图像描述使用pycdc.exe失败。因为错误“不支持的操作码:JUMP_IF_NOT_EXC_MATCH”你知道我为什么失败吗?(我试图编译的.pyc似乎是3.10版本)......
  • D. Fox And Jumping
    原题链接题意简述在序列中选择若干个数,使得其\(gcd=1\)且对应代价最小实施假设答案里,\(a_i\)是最后一个选的,代表\(i\)前面存在某些数的组合的\(gcd\)与\(a_i\)互质背包+状压再遍历前面的数\(j\)和状态,代表选\(j\)时,数\(i\)的质因子集合的状态code#include<......
  • [LeetCode] 45. Jump Game II
    有点意思,需要动态规划。fromtypingimportListfromcollectionsimportCounterimporttimeclassSolution:defjump(self,nums:List[int])->int:max_reachable=0min_steps=0fori,elementinenumerate(nums):i......
  • [LeetCode] 55. Jump Game
    写了一个符和直觉的递归,时间超限了。fromtypingimportListimporttimeclassSolution:defcanJump(self,nums:List[int])->bool:iflen(nums)==1:returnTruereturnself.isreach(nums,0)defisreach(self,nums:List[i......
  • JPS(Jump Point Search)跳点搜索路径规划算法回顾
      本篇文章主要回顾一下几年前学的JPS跳点搜索规划算法的相关内容,之前学的时候没有进行概括总结,现在补上  一、A*算法简单回顾–  1、基本介绍和原理  A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。......
  • [NSSRound#3 Team]jump_by_jump
    Problem:[NSSRound#3Team]jump_by_jump目录思路总结思路jz,jnz经典的花指令,解题思路:将call给硬编码,nop,修复所有黄色字段,在重新生成函数可以解决D-->转换为硬编码此处转化为0E8h了C-->修复汇编语言一点一点修复即可P-->重新生成函数在此处main直接p生成函数即可......
  • goto 语句以及 setjump、longjump 函数的注意事项总结
    关于goto、setjmp、longjmp的注意事项,总结如下:goto语句避免滥用:goto语句虽然能够提供一种直接的跳转方式,但过度使用会使程序结构变得复杂,难以阅读和维护。应优先考虑使用结构化的控制流语句(如if、while、for等)。防止死循环:在使用goto语句时,要特别注意不要形成死......