算法-dp斜率优化
前置知识：
凸包
斜率优化很玄学，凭空讲怎么也讲不好，所以放例题。
[APIO2014]序列分割
给你一个长度为 (n) 的序列 (a_1,a_2,...,a_n)。你可以切 (k) 刀，每一刀可以把某一段序列切成两段，然后获得两段和成绩的收益。最后求最大收益和得到最大收益的切割方案。
数据范围：(2le nle 100000,1le klemin{n-1,200},1le a_ile 10000)。
首先证明，切的顺序不影响结果。设序列为连着的 (a,b,c) 三段。三段的和分别为 (A,B,C)。
如果先切开 (a|b,c) 再切开 (a|b|c)，获益为 (A(B+C)+BC=AB+AC+BC)。
如果先切开 (a,b|c) 再切开 (a|b|c)，获益为 ((A+B)C+AB=AC+BC+AB)。
所以以此类推，切割的顺序不影响最终收益大小。
然后开始 ( exttt{dp})，(F_{i,j}) 表示前 (i) 个数切 (j) 刀的最大收益，(s_i=sumlimits^i_{j=1}a_j)，则有状态转移方程：
因为 (F_{i,j}) 只由 (F_{t,j-1}) 推得，所以可以滚动数组 (F)，令 (f_j=F_{i,j})，(g_j=F_{i,j-1})，那么上式就变成：
如果直接暴力跑一次 (2) 重循环的 ( exttt{dp})，(Theta(n^2k)) 会 (color{#357}{ exttt{TLE}})，但你仔细观察 (g_t+s_t(s_i-s_t)) 这个式子，如果有一个 (p(0le p<i)) 满足
则推式可得：
令 (slope=frac{(g_p-s_p^2)-(g_t-s_t^2)}{s_t-s_p})
如果把 ((-s_p,g_p-s_p^2)) 和 ((-s_t,g_t-s_t^2)) 看作平面直角坐标系中的两个点，那么 (slope) 就是这两个点连边的斜率。
因为 ( exttt{dp}) 循环 (i=1 o n) 时 (s_i) 是递增的，而两个点的 (slope) 又不是随 (s_i) 变化的，所以可以维护一个双头单调队列，每次把 (i) 放到队尾，队列满足：
- 从左到右数递增。
- 从左到右相邻两个数所对应的点连边的斜率递减。
然后维护队列并 ( exttt{dp})：
循环 (j=1 o k)：
赋值滚动数组 (g=f)，清零 (f)。
清空队列并在队列中加入 (0)（相当于原点）。
循环 (i=1 o n)：把队列头相邻两个数 (slopele s_i) 的踢掉。
取队列头 (p)，(f_i=g_p+s_p(s_i-s_p))。
因为最终要输出方案，所以记录索引 (pro_{i,j}=p)。
把 (i) 看作点 ((-s_i,g_i-s_i^2))，如果队尾相邻元素的 (slopege i) 和队尾元素的 (slope)，就把队尾元素踢掉。
队尾加入 (i)。
然后在单调队列和斜率优化的加持下，因为维护队列和循环 ( exttt{dp}) 的总时间复杂度为 (Theta(n))， 所以总的时间复杂度缩减为 (Theta(nk))。于是蒟蒻逃脱了 (color{#357}{ exttt{TLE}}) 的风险。
Code：
#include <bits/stdc++.h>
using namespace std;
/*
{a},{b},{c}
a(b+c)+bc=ab+ac+bc-Greatitude
(a+b)c+ab=ac+bc+ab/-/
*/
#define lng long long
const int N=1e5+10,K=210;
int n,k,a[N],q[N],p[N][K]; //n,k,ai,queue,方案路径
lng f[N],g[N],sum[N]; //fi,gt,si
double funct(int x,int y){ //两个点的slope
if(sum[x]==sum[y]) return -1e16;
return 1.0*((g[x]-sum[x]*sum[x])-(g[y]-sum[y]*sum[y]))/(sum[y]-sum[x]);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",a+i),sum[i]=sum[i-1]+a[i];
for(int j=1;j<=k;j++){ //维护单调队列+dp
for(int i=1;i<=n;i++) g[i]=f[i],f[i]=0;
int l=1,r=0;
q[++r]=0;
for(int i=1;i<=n;i++){
while(l<r&&funct(q[l],q[l+1])<=sum[i]) l++;
f[i]=g[q[l]]+sum[q[l]]*(sum[i]-sum[q[l]]);
p[i][j]=q[l];
while(l<r&&funct(q[r-1],q[r])>=funct(q[r],i)) r--;
q[++r]=i;
}
}
printf("%lld
",f[n]); //输出最终最大收益
for(int i=k,j=n;i>=1;i--)
printf("%d%c",j=p[j][i],"
"[i>1]); //输出切割方案。
return 0;
}
祝大家学习愉快！