我蒟蒻，不知道单调队列是什么……

这题我是这样想的：

用F表示跳到第i个可得到的最多能量，a表示如果不考虑跳跃时消耗的能量，跳到第i个可得到的最多能量（即1~i能量球的和+原始能量），g[i]表示跳到第i个的最少损失（跳跃造成的损失）。显然我们可以得出f[i]:=a[i]-g[i]，故我们求f[i]的过程可以转化为求g[i]的过程。显然g[i]:=min(g[j])+i*100(f[j]>=i*100)，我猜想g是一个升序的序列，所以每次找j不必一个一个地枚举，只需找出满足f[j]>=i*100中最小的j即可，于是就诞生了O(N)算法。

请教大牛下，我的猜想和算法对吗？

呵呵，第175人AC

首先谢谢zztDANTE的题解，让我茅塞顿开，谢谢阿！！！

其次，可以加一个很小的优化，就是所有数据用实数存储，对每个高度获得的能量，（即每个读入数据）都除以100，这样后面就不用再动不动就*100或/100了，少了很多运算

为啥我的这么慢？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

20行不到AC……

单调队列果然强大……

Orz

Orz 单调队列！！

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

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

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

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

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

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

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

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

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

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

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

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

对于本题，光了解解题思想是不够的，要加以转化，并加以实现（否则就不止百把个AC了）

显然，本题要求O(n)算法，而本题的DP是O(n^2)的，所以需要优化。

不妨设：f[h]为跳到h高度后可以得到的最大能量，注意到：

若f[h]是由f[hi]演变而来（即获得hi的最大能量后，再跳到h），那么，不存在h>=hj>=hi，使从f[hj]演变而来的f[h]大于由f[hi]演变而来的f[h]

证明：令sum[n]表示从1至n的能量总和

f=f[hi]+sum[n]-sum[hi]-h*100

f=f[hj]+sum[n]-sum[hj]-h*100

显然f>f

换句话说：对于h，最优解总是来自可以到达h的最小高度

从这个指导思想出发，我有了以下的解法：

f[n]为跳到n高度后可以得到的最大能量

g[n]为可以跳到n高度的最小高度

fillchar g[i]=-1

预处理 i=0

for i:=1 to n do

begin

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

k:=f[i] div 100;

! !

for j:=!i+1 to k! do

if g[j]=-1 then

g[j]:=i

! !

end;

当我写到这里的时候，我得了0分.......

仔细想想，有什么地方错了呢？

首先，对于k,若f[i]很大，k是很容易大于n的，这时其实我们已经找到了到达n高度的最小高度，可以直接输出结果（当然，k=n时也表示找到了这样的高度）。另外，若有一个g[n]-1那么它前面的高度应该都已经赋过值了（而且比当前值小），所以应该从k点往前赋值，并且遇到g[n]-1时跳出

修改了! !中间的部分，得到AC的程序

fillchar(g,sizeof(g),$ff);

g[0]:=0;

k:=f[0] div 100;

for i:=1 to k do

g[i]:=0;

for i:=1 to n do

begin

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

k:=f[i] div 100;

if k>=n then begin

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

writeln(f[n]);exit;

end;

for j:=k downto i+1 do

if g[j]=-1 then

g[j]:=i

else break;

end;

DP+单调队列

f[i]:表示前i次跳跃能吃的最大能量值

sum[i]:表示前i次跳跃的能量值

q[l..r]:表示前i-1次跳跃结束后的最大值

(每次对第i个数进行调整，l取min{l | f[q[l]]>=i*100})

此时,f[i]:=f[q[l]]+sum[i]-sum[q[l]]-i*100;

Ans:=f[n]

成功得解决了时间复杂度的问题 O(NlogN)

g[i] 表示第i次是从g[i]跳过来的。

f[i] 为跳到i的所剩的最大能量。

每次从i-1次跳到的点开始枚举。

如果(f[j]>=i*100)跳的到i就附值。

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

g[i]:=j;

单调队列果然是个好东西，从这个题学了很多

ORZ教主

我用的是二分，但我不知道对不对，考试时一个都没过，不知道是我写错了，还是算法本身有问题

队列如何维护啊

orz

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

二十几行代码!!

但是我的跟 zgx大牛的有点不同

方程是一样的

但是我是将f加入队尾

inc(op);

t[op]:=i-1;

运气不错 AC了``

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第66个AC!

算法：

方程是 F=F[J]+SUM-SUM[J]-I*100 ；

用一个队列优：

每次从队头开始找一个j可以到达i，并把j之前的都删掉，

如果f[i]>f[队尾的那个],那么i就入队。

最后答案是f[n].

算法证明在下面这位。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

RP不太好

F=F[J]+SUM-SUM[J]-I*100

F[J]-I*100>0

I>J>0

用一个queue维护f中的递增队列。IMJGOOD已经给了详细的说明

每次从开头找到能跳到i的值就可以了

注意 sum要预处理。

Orz.

我用单调队列乱搞的就AC了……

F [ I ] 表示的是最后一次跳跃至I能保留的最大能量值. SUM[ I ]表示从1~I的能量球总和

那么转移是 F [ I ] = F [ J ] + SUM [ I ] - SUM [ J ]-I*100

前提是F [ J ] >= i * 100 (不然跳不到);

那么对于K1 < K2

设F [ I ]由K 转移来的值为S ( K , I ),那么如果有S ( K1 , I ) SUM [ K2 ] - SUM [ K1 ]

也就是说当 S ( K2 , I ) > S ( K1 , I ) (可以推广到任意I因为F [ K ] - SUM [ K ] 与 I 无关), 必有F [ K2 ] > F [ K1 ] 那么显然不论怎么样 K2 都比K1优,以后也是如此,所以删除K1,如果S ( K2 , I ) < S ( K1 , I ) 那么我们判断如果F[ K2 ] < F[ K1 ] 则删除K2,否则保留,保留的结果按K1

先来占个位，考试时就这题来不及做

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

维护一个O(n)的队列即可,

WS的开了600W...哈哈

把DP方程优化一下就变成递减的了然后就可以O(n)…