A27702. 跳跃(jump)
填空题
中等
知识点
题目描述
跳跃(jump)
题目描述
猴子的正上方，每1米处，都有一个桃子，一共有N个桃子，每个桃子都有其能量值，摘下这个桃子吃下就获得了这个能力值。猴子每跳1米会消耗1个点能量，在能量值允许的下，它可以跳到任何一个可以到达的高度，并且将这个高度及以下高度的桃子摘下吃掉。确保猴子初始的能量一定可以摘下所有的桃子。求该猴子摘下吃掉所有的桃子后，保留最多的能量值
输入格式
第一行 两个整数N和M,表示桃子的数量和猴子的初始能量
第二行，N个非负整数，依次描述从下向上描述各桃子的能量值。
输出格式
一个整数，意义如题所述。
输入输出样列
输入样例1
3 2
2 2 2
输出样例1
4
说明
1<=N <=2000000
参考答案
#include<bits/stdc++.h>
using namespace std;
long long sum[2000005],f[2000005], ans, a; // f[i]: 够到第 i 个桃子时，能保留的最大能量
long long s, n;
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
scanf("%d",&a);
sum[i]=sum[i-1]+a; // 前缀和，sum[i]: 够到第 i 个桃子时，能获取的最大能量值
}
f[0]=s; // 还没开始够，最大能量就是初始能量
for(int i=1,j=0;i<=n;i++){
while(f[j]<i)j++; // 只要能量还能够到第 i 个桃子，就去够，这样才能尽量少跳（消耗能量）
// 跳一次够第 i 个桃子前，上一次跳，够到第 j 个桃子最划算
f[i] = f[j] + (sum[i]-sum[j]-i); // 能够增加的能量 = 够到的桃子的能量-跳到 i 米高消耗的能量
}
cout<<f[n];
}
上一题
下一题