斜率优化的经典模型，将序列分成若干段，每段有一个权值计算方法，求权值和最大/小
暴力的dp $O(n^{2})$
dp[i]为1-i的序列的最优解。sum[i]为前缀和,$D(i)=ax^{2}+bx+c$
转移为$dp[i]=\max_{j=0}^{i-1}dp[j]+D(sum[i]-sum[j])$
然后叒是经典的推公式：
设$j<k<i$，且i从k转移比i从j转移更优。
$dp[j]+a(sum[i]-sum[j])^{2}-b(sum[i]-sum[j])+c<dp[k]+a(sum[i]-sum[k])^{2}-b(sum[i]-sum[k])+c$
$dp[j]+asum[j]^{2}-bsum[j]-(dp[k]+asum[k]^{2}-bsum[k])>2asum[i](sum[j]-sum[k])$
$\frac{dp[j]+asum[j]^{2}-bsum[j]-(dp[k]+asum[k]^{2}-bsum[k])}{sum[j]-sum[k]}>2asum[i]$
设 $f[j]=dp[j]+sum[j]^{2}-bsum[j]$ $T[j]=sum[j]$
$\frac{f[j]-f[k]}{T[j]-T[k]}>2asum[i]$
将$(T[j],f[j])$,$(T[k],j[k])$看成二维平面上的点。所以当斜率$K_{jk}>2asum[i]$时，从dp[k]转移比dp[j]更优。
所以用优先队列维护最优的点集，就A了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e6 + 10; 5 ll sum[maxn], q[maxn], dp[maxn], que[maxn]; 6 int n, a, b, c; 7 ll f(int j, int k) { 8 return dp[j] + a * sum[j] * sum[j] - b * sum[j] - (dp[k] + a * sum[k] * sum[k] - b * sum[k]); 9 } 10 ll T(int j, int k) { 11 return sum[j] - sum[k]; 12 } 13 ll D(int x) { 14 return a * x*x + b * x + c; 15 } 16 int main() { 17 scanf("%d", &n); 18 scanf("%d%d%d", &a, &b, &c); 19 for (int i = 1; i <= n; i++) 20 scanf("%lld", &q[i]), sum[i] = sum[i - 1] + q[i]; 21 int l = 1, r = 1; 22 que[l] = 0; 23 for (int i = 1; i <= n; i++) { 24 while (l < r&&f(que[l + 1], que[l]) >= 2 * a*sum[i] * T(que[l + 1], que[l])) 25 l++; 26 dp[i] = dp[que[l]] + D(sum[i] - sum[que[l]]); 27 while (l < r && f(que[r], que[r - 1])*T(i, que[r]) < T(que[r], que[r - 1])*f(i, que[r])) 28 r--; 29 que[++r] = i; 30 } 31 printf("%lld\n", dp[n]); 32 }