题意描述

LHX教主很能跳，因为Orz他的人太多了。

教主跳需要消耗能量，每跳$1$米就会消耗$1$点能量，如果教主有很多能量就能跳很高。

教主为了收集能量，来到了一个神秘的地方，这个地方凡人是进不来的。

在这里，教主的正上方每$100$米处就有一个能量球（也就是这些能量球位于海拔$100，200，300$……米处。

每个能量球所能提供的能量是不同的，一共有$N$个能量球（也就是最后一个能量球在$N×100$米处）。

教主为了想收集能量，想跳着吃完所有的能量球。

教主可以自由控制他每次跳的高度，接着他跳起把这个高度以下的能量球都吃了，他便能获得能量球内的能量，接着吃到的能量球消失。

教主不会轻功或二段跳，所以教主不能因新吃到的能量而变化此次跳跃的高度。

并且教主还是生活在地球上的，所以教主每次跳完都会掉下来。

问教主若要吃完所有的能量球，最多还能保留多少能量。

输入格式

第1行包含两个正整数$N$，$M$，表示了能量球的个数和LHX教主的初始能量。

第2行包含$N$个非负整数，从左到右第$i$个数字依次从下向上描述了位于$i×100$米位置能量球包含的能量，每两个整数之间用一个空格隔开。

输出格式

仅包括一个非负整数，为教主吃完所有能量球后最多保留的能量。

Input & Output ‘s examples

Input ‘s eg

3 200
200 200 200

Output ‘s eg

数据范围与约定

对于$10\%$的数据，有$N≤10$；

对于$20\%$的数据，有$N≤100$；

对于$40\%$的数据，有$N≤10^3$；

对于$70\%$的数据，有$N≤10^5$；

对于$100\%$的数据，有$N≤2 \times 10^6$。

保证对于所有数据，教主都能吃到所有的能量球，并且能量球包含的能量之和不超过$2^31-1$。

分析

一道简单DP。~~但我考场没过~~

认真读题，不难看出题目中让我们最大化最后剩下的能量之和。也就是最大化得到的能量 - 失去的能量。

而得到的能量之和是固定的。因此，我们只能尽量少失去能量。

失去能量多少的决定于两点：跳跃次数与跳跃高度。相比之下，跳跃次数的影响更大。

也就是说，我们要尽量的少跳，即在能量够用的情况下尽量吃到更多的能量球。

考虑$dp$，设$f[i]$为吃到第$i$个能量球后能保留的最大能量，则最终状态为$f[n]$

转移时，枚举上一次到达的能量球是第几个，设其为$p$，可得

$f[i] = max(f[i] , f[p] + b[i] - b[p] - i * 100)$

其中，$b$为前缀和数组，用于表示从$1$跳到$n$可以得到的能量数。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 2000001

using namespace std;

int f[N] , a[N] , b[N];
int n , m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    b[1] = a[1];
    for(int i = 2; i <= n; i ++){   //处理前缀和
        b[i] = b[i - 1] + a[i];
    }
    f[0] = m;   //若不跳，则最大能量即为初始能量。
    int cnt = 0;    //记录当前跳到的能量球，相当于题解中的p
    for(int i = 1; i <= n; i ++){
        while(f[cnt] < i * 100){ 
            cnt ++; //如果获得的能量不足以向上跳到第i个能量球，就考虑多得到一个能量球后在向上跳
        }
        f[i] = f[cnt] + b[i] - b[cnt] - i * 100;
    }
    cout << f[n] << "\n";
    return 0;
}