Luogu

BZOJ

分析

先考虑一个 $O(n^2)$ 的暴力DP。

设 $f[i]$ 表示 $1\sim i$ 的最大值。

再设题目中的二次函数是 $F(i)$ ,$sum$ 是 $x$ 的前缀和,然后容易得到:

$$ \displaystyle f[i]=\max\limits_{j=0}^{i-1}\left\{f[j]+F(sum[i]-sum[j])\right\} $$

考虑斜率优化。

假设 $j$ 比 $k$ 更优,那么

$$ f[j]+F(sum[i]-sum[j])>f[k]+F(sum[i]-sum[k]) $$

把二次函数代进去并化简

$$ f[j]+Asum[j]^{2}-2Asum[i]sum[j]-Bsum[j]>f[k]+Asum[k]^{2}-2Asum[i]sum[k]-Bsum[k] $$

再化简一下

$$ sum[i]>\frac{(f[j]+Asum[j]^{2}-Bsum[j])-(f[k]+Asum[k]^{2}-Bsum[k])}{2A(sum[j]-sum[k])} $$

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

int n,A,B,C;
int sum[MAXN];
int f[MAXN];
int Q[MAXN],h=1,t=1;

inline int F(int x) {
    return A*x*x+B*x+C;
}

inline double slope(int i,int j) {
    int up=(f[i]+A*sum[i]*sum[i]-B*sum[i])-(f[j]+A*sum[j]*sum[j]-B*sum[j]);
    int down=2*A*(sum[i]-sum[j]);
    return 1.0*up/down;
}

mainint main() {
    n=read(),A=read(),B=read(),C=read();
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    for (re int i=1;i<=n;++i) {
        while (h<t&&slope(Q[h],Q[h+1])<=sum[i]) ++h;
        f[i]=f[Q[h]]+F(sum[i]-sum[Q[h]]);
        while (h<t&&slope(Q[t-1],Q[t])>=slope(Q[t],i)) --t;
        Q[++t]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 55 PM