http://www.lydsy.com/JudgeOnline/problem.php?id=1911?(題目鏈接)
題意
給出一個序列，將序列分成連續的幾段，每段的價值為a*s*s+b*s+c，其中a,b,c為給定常數，s為這一段中所有數之和。求最大價值和。
Solution
斜率優化。
dp方程：$${f[i]=max(f[j]+a*(s[i]-s[j])^2+b*(s[i]-s[j])+c)}$$
其中${s[i]}$為前綴和，${f[i]}$表示從1~i的最大價值。
斜率式：$${s[i]*(2*a*s[j])+f[i]=(f[j]-b*s[j]+a*s[j]^2)+a*s[i]^2+b*s[i]+c}$$
所以決策${j}$映射到平面直角坐標系上就是：${(2*a*s[j],f[j]-b*s[j]+a*s[j]^2)}$。斜率：${s[i]}$為正且單增；橫坐標${2*a*s[j]}$單減（${a}$小于0，${s[j]}$單增），所以單調隊列里面的點長成這樣：
?
細節
開long long。
代碼
// bzoj1911
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;const int maxn=1000010;
LL f[maxn],s[maxn],a,b,c;
int n,q[maxn];double slope(int i,int j) {return (double)((f[i]-b*s[i]+a*s[i]*s[i])-(f[j]-b*s[j]+a*s[j]*s[j]))/(double)((2*a*s[i])-(2*a*s[j]));
}
int main() {scanf("%d",&n);scanf("%lld%lld%lld",&a,&b,&c);for (int i=1;i<=n;i++) scanf("%lld",&s[i]),s[i]+=s[i-1];int l=1,r=1;q[1]=0;for (int i=1;i<=n;i++) {while (l<r && slope(q[l],q[l+1])<=s[i]) l++;f[i]=f[q[l]]+a*(s[i]-s[q[l]])*(s[i]-s[q[l]])+b*(s[i]-s[q[l]])+c;while (l<r && slope(q[r-1],q[r])>slope(q[r],i)) r--;q[++r]=i;}printf("%lld",f[n]);return 0;
}
