2021年庐阳区青少年信息学科普日真题- 跳跃（jump)
题目描述
猴子的正上方，每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;
}