[BZOJ 1911] 特别行动队-白红宇

[BZOJ 1911] 特别行动队

阅读量：4703 次

发布时间：2019-06-09

本文共 1660 字，大约阅读时间需要 5 分钟。

Link:

Algorithm:

DP方程：$dp[i]=max(dp[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)$

方程是显然的，但复杂度为$O（N^2）$，需要优化到$O（N）$，这时就需要斜率优化了

推荐博客：https://www.cnblogs.com/MashiroSky/p/6009685.html

这篇博客清晰地从“数”到“形”展现了斜率优化

其中必要的前提：dp数组是要具有决策单调性的

（即如果在$dp[i]$下决策$j$好于$k$，那么在大于$i$时$j$永远要好于$k$）

同时与i相关的数组具有单调性（不具有决定性，可以通过凸包二分来解决非单调性问题）

此题符合这几个前提，

如果$j>k$且$j$比$k$更优：（由决策单调性推出）

$dp[j]-dp[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i]$

$slope(j,k)=\frac{dp[j]-dp[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])}{2*a*(sum[j]-sum[k])}>sum[i]$

用单调队列维护$slope$

1、使$slope（cur,cur+1）$保持递增，因为$sum[i]$递增

2、由于$slope（j，k）>sum[i]$时决策$j$比$k$更优，因此决策$head$>$head+1$>……$tail$

每次将$slope(head,head+1) < sum[i]$的$head$踢出队列，之后的$queue[head]$即为最优决策

记住，SLOPE只是用于判断在$sum[i]$时$j$比$k$优的结论是否成立，我们用优先队列来优化维护其的复杂度

$slope(j,k)$和$slope(j'' , k'')$间的大小关系与决策的优越性不具有直接联系

Code:

#include 
     
      using namespace std;typedef long long ll;const int MAXN=1e6+10;ll pre[MAXN],dp[MAXN],que[MAXN],l,r,a,b,c,n;inline ll read(){    char ch;ll num,f=0;    while(!isdigit(ch=getchar())) f|=(ch=='-');    num=ch-'0';    while(isdigit(ch=getchar())) num=num*10+ch-'0';    return f?-num:num;}ll sqr(ll x){
    return x*x;}inline double slope(int x,int y){    return (double)(dp[x]-dp[y]+a*sqr(pre[x])-a*sqr(pre[y])+b*(pre[y]-pre[x]))/(double)(2*a*(pre[x]-pre[y]));}int main(){    n=read();a=read();b=read();c=read();    for(int i=1;i<=n;i++) pre[i]=read(),pre[i]+=pre[i-1];        for(int i=1;i<=n;i++)    {        while(l