首页 > 代码库 > Vijos1617 超级教主

Vijos1617 超级教主

传送门@百度。。

 

背景

Orz4-3 jump

描述

LHX教主很能跳,因为Orz他的人太多了。教主跳需要消耗能量,每跳1米就会消耗1点能量,如果教主有很多能量就能跳很高。

教主为了收集能量,来到了一个神秘的地方,这个地方凡人是进不来的。在这里,教主的正上方每100米处就有一个能量球(也就是这些能量球位于海拔 100,200,300……米处),每个能量球所能提供的能量是不同的,一共有N个能量球(也就是最后一个能量球在N×100米处)。教主为了想收集能 量,想跳着吃完所有的能量球。教主可以自由控制他每次跳的高度,接着他跳起把这个高度以下的能量球都吃了,他便能获得能量球内的能量,接着吃到的能量球消 失。教主不会轻功,教主不会二段跳,所以教主不能因新吃到的能量而变化此次跳跃的高度。并且教主还是生活在地球上的,所以教主每次跳完都会掉下来。

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

格式

输入格式

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

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

输出格式

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

样例1

样例输入1[复制]

3 200200 200 200

样例输出1[复制]

400

限制

对于10%的数据,有N≤10;
对于20%的数据,有N≤100;
对于40%的数据,有N≤1000;
对于70%的数据,有N≤100000;
对于100%的数据,有N≤2000000。

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

时限1s。

提示

第1次跳100米,得到200能量,消耗100能量,所以落地后拥有300能量。

第2次跳300米,吃到剩下的第3棵能量球,消耗拥有的300能量,得到400能量。

若第1次跳200米,第2次跳300米,最后剩余300能量。

 

这些天一直没做题。。感觉状态真是不能更逗比。

单调队列的裸题

#include<set>#include<queue>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 2000010;#define Rep(i,n) for(int i=1;i<=n;i++)#define For(i,l,r) for(int i=l;i<=r;i++)int A[N],sum[N],n,m,q[N],dp[N];int main(){    scanf("%d%d",&n,&m);    Rep(i,n){        scanf("%d",&A[i]);        sum[i]+=sum[i-1]+A[i];    }    dp[0]=m;    int Left=0,Right=0;    Rep(i,n){        while(Left<Right&&dp[i-1]-sum[i-1]>dp[q[Right-1]]-sum[q[Right-1]]) Right--;        q[Right++]=i-1;        dp[i]=dp[q[Left]]+sum[i]-sum[q[Left]]-i*100;        while(Left<Right&&dp[q[Left]]-(i+1)*100<0) Left++;    }    printf("%d\n",dp[n]);    return 0;}

 

Vijos1617 超级教主