JZYZOJ 1326 超级教主

---

题解

首先向考虑小范围的数据。

\(a[i]\)表示前\(i\)个球的总能量，一个前缀和很好理解的

\(f[i]\)表示获得第\(i\)个球后的总能量

呢么很显然我们可以\(DP\)了！！

f[i] = max(f[j] + a[i]-a[j] - 100*i)

呢么这就是一个\(O(n^2)\)的算法。很显然过不了。

呢么自然而然就是优化

常见的优化就是压维。

好吧，单调性优化

我们发现查找\(j\)是很费时的，我们可不可以用\(O(1)\)的办法把\(j\)找出来呢？？？

首先我们用一个队列来储存\(j\)的最优值，每次取队头就好了

呢么我们怎么更新队列呢

队头简单如果\(f[j]\)的能量小于当前\(i\)的高度更新掉就好了

队尾比较难理解先看代码

while(f[i] - a[i] > f[q[r]] - a[q[r]]) r--;

\(f[i] - a[i]\) 就是已经获得\(i\)的能量后，损失能量的总和的相反数

很自然\(i\)损失的能量小于\(q[r]\)的能量肯定要舍弃队尾

因为是相反数，所以要变成大于(不等式的性质，不等式两侧同乘一个负数，不等式要变号)

---

coding

#include <bits/stdc++.h>
using namespace std;


const int N = 2000005;
int n,f[N] = {},a[N] = {};
int cnt,ans = 0,q[N] = {},l = 0,r = 1;


inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        x = (x<<3)+(x<<1) + ch-'0';
        ch = getchar();
    }
    return x;
}


int main()
{
    n = read(); f[0] = read();
    for(register int i = 1;i <= n;i++) a[i] = a[i-1] + read();

    for(register int i = 1;i <= n;i++)
    {
        while(f[q[l]] < 100*i && l < r) l++;
        f[i] = f[q[l]] + a[i]-a[q[l]] - 100*i;
        while(f[i] - a[i] > f[q[r]] - a[q[r]]) r--;
        q[++r] = i;
    }

    printf("%d\n",f[n]);
    return 0;
}