简单推了推，发现就是单调DP。

说下思路吧，题中说我们只能获得 “一次能量球的值” ，但是我们的跳是可以跳多次的。解题的关键在于我们必须尽量减少 “跳跃时的代价” ，所以我们不会做出以下决策。

1. 后次的跳跃高度比前次的还低或相等。
2. 刚拿到能量就让自己跳到最高。（这是一种贪心策略，实际一般会错误）

想到我们在达到我们的最大高度前想要尽可能的保留更多的能量，我们容易想到用dp实现。

F[i] 表示吃到第i高的能量球时体力的最大值，易知转移。

F[i] = F[j] + A[i]-A[j]（A用于保存前缀和，表示这一次跳跃获得的能量）+ i * 100（跳跃的代价）（0<=j<=i）

由以上转移方程可知，F[i]的负代价与j无关，而正代价随j的减少而增大（因为能量一定为正）
，于是用单调队列，保存能够跳跃到当前点的最小状态转移即可。

#include <cstdio>
#include <iostream>
using namespace std;
int N, M;
int A[2000005], F[2000005];
int Q[2000005], L, R;
int main () {
    
    cin >> N >> M;
    A[0]=F[0]=M;
    for(int i=1; i<=N; i++) cin >> A[i], A[i]+=A[i-1];
    L=1, R=0, Q[R]=0;
    for(int i=1; i<=N; i++) {
        while(i*100>F[Q[R]]&&R<L) R++;  
        Q[L++]=i;
        F[i]=F[Q[R]]+(A[i]-A[Q[R]])-i*100;
    }
    cout << F[N];
    return 0; 
    
}

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int s[2000005],f[2000005],i,j,k,n,m,q[2000005],l,r;
int main()
{
scanf("%d%d",&n,&f[0]);
q[1]=0;l=1;r=1;
for(i=1;i<=n;i++)
{
scanf("%d",&s[i]);
s[i]+=s[i-1];
}
for(i=1;i<=n;i++)
{
while(l<=r&&f[q[l]]<i*100) l++;
f[i]=f[q[l]]-s[q[l]]+s[i]-i*100;
while(l<=r&&f[q[r]]-s[q[r]]<=f[i]-s[i]) r--;
q[++r]=i;

}
printf("%d",f[n]);
return 0;
}

#include<cstdio>
using namespace std;
#define N 2e6+5
long long a[(int)N];
long long dp[(int)N];
using namespace std;
long long nextInt() {
long long x;
char c;
do c=getchar(); while (c<'0'||c>'9');
x=c-'0';
while ('0'<=(c=getchar())&&c<='9') x=x*10+c-'0';
return x;

}

int main()
{

int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
long long x=nextInt();
a[i]=a[i-1]+x;
}
dp[0]=m;
int i=0;
for(int j=1;j<=n;j++)
{
while(dp[i]<j*100) i++;
dp[j]=dp[i]+a[j]-a[i]-j*100;
}

printf("%lld\n",dp[n]);
return 0;
}

单调队列优化Dp

int main()
{
    scanf("%d%d",&n,&f[0]);
    For(i,1,n)  scanf("%d",&p),sum[i]=sum[i-1]+p;
    l=1;r=1;q[1]=0;v[1]=f[0];
    For(i,1,n)
    {
        while(l<r&&f[q[l]]<i*100)   l++;
        f[i]=+sum[i]+v[l]-i*100;
        int tv=f[i]-sum[i];
        while(l<r&&tv>v[r]) r--;
        q[++r]=i;v[r]=tv;
    }
    printf("%d\n",f[n]);
}

//DP嘛；
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long
#define M 2000001
LL n,m,i,x,h,l;
LL f[M],s[M]={0},num[M];
void init()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);
        s[i]=s[i-1]+x;
    }
    return;
}

void dp()
{
    h=1,l=0;
    num[h]=0;
    f[0]=m;
    for (i=1;i<=n;i++)
    {
        while (f[num[h]]<i*100 && h<=l)
            h++;
        f[i]=f[num[h]]+s[i]-s[num[h]]-i*100;
        if (f[i]>f[num[l]])
        {
            l++;
            num[l]=i;
        }
    }
    return;
}
int main()
{
    init();
    dp();
    cout<<f[n]<<endl;
}

教主飞了……

没有单调队列。，。，。。，用了个flag 也是n吧。，。，但是时间1600++不知道为什么？？

记录页面看到评测机是 Vijos Mini 70分

点进去变成 Ed***|**，100分

退回页面刷新，成了 100分

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

话说，数据类型很重要。。

int64或者double就超时了，所以我严格限制每一个数的范围

改用longint的就用long，改用word的就用word

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：325ms

一次AC,爽！可惜时间....囧~~~

单调队列是个好东西啊！

教主好能跳 要是有第一宇宙速度就好了 直接 去火星（时间好像有点久）深造

不用单调队列的..

f[i]:=max{f[j]+sum[i]-sum[j]-i*100=sum[i]-i*100-(sum[j]-f[j])=常数-(到达J的消耗)},f[j]>=i*100

显然 对于J递增,到达J的消耗递增,因为高度增加..

那么f[i]就是关于j的递减函数,这样就不需要用到队列,只要一个指针p指向满足f[j]>=i*100的最小的J就可以了.

for i:=1 to n do begin

while f[p]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 869ms

├ 测试数据 09：答案正确... 775ms

├ 测试数据 10：答案正确... 853ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2497ms

sunny 好慢

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

弱弱的问一句.. 什么是单调队列??

var i,j,k,l,m,n,oo,a:longint;

f,sum:Array[0..2000000]of longint;

begin

readln(n,m);

f[0]:=m;

for i:=1 to n do

begin

read(a);

sum[i]:=sum+a;

for j:=oo to i-1 do

if f[j]>=i*100 then

begin

oo:=j;

f[i]:=f[j]+sum[i]-sum[j]-i*100;

break;

end;

end;

writeln(f[n]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：122ms

我让此题通过率增加一个百分点！

单调队列.......

就是可以删头然后加入尾的咯，

保证要加入的元素大于队尾元素

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 806ms

├ 测试数据 09：答案正确... 853ms

├ 测试数据 10：答案正确... 822ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2481ms

sunny进步了，本来会超

我们伟大的yz的LHX教主啊！！！

OrzING！！！

单调队列...

折腾死我了。

动态转移方程是

f[i]=max(f[j]+sum[i]-s[j])-i*100

考虑每一个在1..i-1的j

如果f[j]=i*100，考虑到跳到同一个高度的获得的能量总和是一定的，那么消耗的能量越少，当前的能量越多。那么显然对于j1