描述
LHX教主很能跳,因为Orz他的人太多了。教主跳需要消耗能量,每跳1米就会消耗1点能量,如果教主有很多能量就能跳很高。
教主为了收集能量,来到了一个神秘的地方,这个地方凡人是进不来的。在这里,教主的正上方每100米处就有一个能量球(也就是这些能量球位于海拔100,200,300……米处),每个能量球所能提供的能量是不同的,一共有N个能量球(也就是最后一个能量球在N×100米处)。教主为了想收集能量,想跳着吃完所有的能量球。教主可以自由控制他每次跳的高度,接着他跳起把这个高度以下的能量球都吃了,他便能获得能量球内的能量,接着吃到的能量球消失。教主不会轻功,教主不会二段跳,所以教主不能因新吃到的能量而变化此次跳跃的高度。并且教主还是生活在地球上的,所以教主每次跳完都会掉下来。
问教主若要吃完所有的能量球,最多还能保留多少能量。
格式
输入格式
第1行包含两个正整数N,M,表示了能量球的个数和LHX教主的初始能量。
第2行包含N个非负整数,从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含的能量,整数之间用空格隔开。
输出格式
仅包括一个非负整数,为教主吃完所有能量球后最多保留的能量。
限制
对于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能量。
题意:略
思路: DP + 单调队列
数据规模是2000000, 只能用一维DP。
dp[i] 表示 吃完前i个, 剩下最大的能量.
先想个 O(N^2)的。
dp[i] = max(dp[i], dp[j]
+ sum[i] - sum[j] - i * 100);
化简为 dp[i] = max(dp[i], dp[j] - sum[j]) + sum[i] - i * 100;
因为每次都是找 Max(dp[j] - sum[j]); 而且要花费N次。 但是, i, i + 1 找的区间只是错开一位。
所以可以用队列优化。维护一个单调递减队列。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <cmath> using namespace std; //单调性DP const int V = 2000000 + 50; const int MaxN = 80 + 5; const int mod = 10000 + 7; const __int64 INF = 0x7FFFFFFFFFFFFFFFLL; const int inf = 0x7fffffff; int dp[V], sum[V]; //dp[i] 表示吃完前i个, 剩余的最大能量 int m, n; int Que[V], front, rear; //单调递减队列优化 Max(dp[j] - sum[j]); void pushBack(int i) { while(front < rear && dp[i] - sum[i] > dp[Que[rear - 1]] - sum[Que[rear - 1]]) rear--; Que[rear++] = i; } int Get(int i) { while(front < rear && dp[Que[front]] < i * 100) //去掉无法到达该高度 front++; return Que[front]; } int main() { int i, j; scanf("%d%d", &n, &m); for(i = 1; i <= n; ++i) { int temp; scanf("%d", &temp); sum[i] = sum[i - 1] + temp; } dp[0] = m; Que[rear++] = 0; for(i = 1; i <= n; ++i) { int id = Get(i); if(dp[id] >= i * 100) dp[i] = max(dp[i], dp[id] + (sum[i] - sum[id]) - i * 100); pushBack(i); } printf("%d\n", dp[n]); }