超级教主

描述

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

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

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

输入

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

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

输出

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

输入样例 1

3 200 
200 200 200

输出样例 1

400

数据范围补充:

先考虑部分数据考试的时候只想到这样了

$b[i]$数组完成前缀和,表示前$i$个能量球的总能量值。

$dp[i]$则表示吃掉第$i$的能量球之后能获得的最大能量值,输入的$m$自然就是$dp[0]$的值。

然后就走上了不归路开始$DP$。

首先想到的是在外层$1->n$循环中套一层$1->(i-1)$,$DP$式子长这样:$dp[i]=max(dp[i],dp[j]-100*i+b[i]-b[j])$

这个式子应该容易理解。本质是让每一个$dp[i]$从比它低的位置跳上来,然后将结果与它打擂,但是时间复杂度达到了$O(n^2)$n方过百万,暴力碾标算

很明显,这个时间复杂度是过不了这道题目的(为什么考试的时候没有数据范围)

那就只能优化


为什么时间复杂度会达到$O(n^2)$?

内层循环花费了太多时间在寻找那个合适的$j$上。那我们能不能在较短时间内找到那个合适的$j$呢?

玩贪心!

既然这么能跳,我就让你跳个够!

因为总能量是有限的,所以能尽量少跳总是好的。所以我们的$j$只需要满足以下条件:

1.$dp[j]$的值足以支持教主跳到第i层。

2.$j$是满足条件1的数中最小的(已经跳的次数最小)

所以,在第一层循环中开一个$while$找到$j$就可以了。

时间复杂度不明


#include<bits/stdc++.h>
using namespace std;
int n,m,val,b[2000010],dp[2000010];
int main()
{
    cin>>n>>dp[0];
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val);
        b[i]=b[i-1]+val;
    }
    int j=0;
    for(int i=1;i<=n;i++)
    {
        while(dp[j]<i*100)
            j++;
        dp[i]=dp[j]-i*100+b[i]-b[j];
    }
    cout<<dp[n]<<endl;
    return 0;
}
最后修改:2020 年 04 月 10 日 06 : 16 PM