斜率优化：
额...这是篇7个题的题解...
首先说说斜率优化是个啥，额...
f[i]=min(f[j]+xxxx(i,j)) ; 1<=j<i （O(n^2)暴力）这样一个式子，首先，如果xxxx（xxx）与j无关，那么这是一个单调队列（可以理解？）
那么我们思考一下，如果xxxx（xxx）与i,j同时相关，如何将其变成类似于单调队列的形式，从而O（n）求解
针对每一个同时有关i,j的变量，我们不妨将j的部分看做j，xx（j）和0,xx（i）对应的直线的斜率，针对而完全与i相关的变量可以无视，计算中加上或减去即可（就是单调队列），而完全与j相关的变量则可以看做是是对应直线在j点的纵坐标，即：xx（j）
那么，问题转化为了已知i-1个直线的斜率以及其上某一点的坐标，求所有直线的最大截距
那么我们思考如何用单调队列维护这一信息：我们通常用队尾的弹出操作维护的斜率单调不下降或单调不上升，因此我们可以用j这个点更新i需要满足Y（j）+K（j）*（和i相关的变量）最大，并且如果在第i个点不满足，那么第i+1的点一定也不满足（点的横坐标单调不下降或单调不上升）因此，我们可以推出单调队列弹出的条件，即：B(i,h)<B(i,h+1)或者B(i,h)>B(i,h+1)，这样就可以用单调队列维护相关信息，O(n)处理求解。
下面是七道题的题解：（代码不是很难写，但是稍微丑了点）
（1）Apio2011 特别行动队 （斜率优化入门题）
DP方程暴力的很好想，f[i]表示前i个人组成特别行动队的最大战斗力和，那么f[i]=a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c+f[j]
化简整理：f[i]-a*sum[i]^2-b*sum[i]=-2*a*sum[j]*sum[i]+f[j]+a*sum[j]*sum[j]-b*sum[j]+c
因此我们可以发现，Y(i,j)=f[i]-a*sum[i]^2-b*sum[i]，K(j)=-2*a*sum[j]，B(j)=f[j]+a*sum[j]*sum[j]-b*sum[j]+c
那么我们可以通过斜率优化完成，K(j)单调递减，x(i)单调递增，这样维护队尾信息的时候，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。
附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 1000005
#define ll long long
#define K(x) (-2ll*a*sum[x])
#define B(x) (f[x]+a*sum[x]*sum[x]-b*sum[x])
#define Y(x,y) (K(y)*sum[x]+B(y))
ll f[N],sum[N],a,b,c;
int q[N],n;
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d",&n);
scanf("%lld%lld%lld",&a,&b,&c);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h])<Y(i,q[h+1]))h++;
f[i]=Y(i,q[h])+a*sum[i]*sum[i]+b*sum[i]+c;
while(h<t&&cmp(i,q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld
",f[n]);
return 0;
}
（2）HNOI2008 玩具装箱 （斜率优化入门题）
n^2DP方程还是很好想的，f[i]表示前i个玩具装箱的最小费用为多少
转移：f[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)^2};（sum[i]为c[i]的前缀和）
那么，为了简化一下方程，我们令a[i]=c[i]+1,sum[i]变为a[i]的前缀和，从而得到：
f[i]=min{f[j]+(sum[i]-sum[j]-(L+1))^2};之后另L++，得到，f[i]=min{f[j]+(sum[i]-sum[j]-L)^2};
展开，整理得到
f[i]-sum[i]^2+2*L*sum[i]=-2*sum[i]*sum[j]+f[j]+sum[j]^2+L^2+2*sum[j]*L;
从而，我们令K(j)=-2*sum[j],B(j)=f[j]+sum[j]^2+L^2+2*sum[j]*L,Y(i,j)=f[i]-sum[i]^2+2*L*sum[i];
那么，K(j)单调递减，sum[i]单调递增，那么维护队尾信息时，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)>Y(h+1)那么弹出。
附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 50005
#define ll long long
#define K(x) (-2ll*sum[x])
#define B(x) (f[x]+sum[x]*sum[x]+2*L*sum[x]+L*L)
#define Y(x,y) (K(y)*sum[x]+B(y))
ll f[N],sum[N],L;
int q[N],n;
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d%lld",&n,&L);L++;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);x++;
sum[i]=sum[i-1]+x;
}
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h])>Y(i,q[h+1]))h++;
f[i]=Y(i,q[h])+sum[i]*sum[i]-2*L*sum[i];
while(h<t&&cmp(i,q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld
",f[n]);
return 0;
}
（3）ZJOI2007 仓库建设 （斜率优化常见题）
这个DP方程需要稍微推一下，大概想想就应该能推出来。
我们考虑如何求将前n个点所有物品全部放在第n个位置的花费，我们需要维护一个sum[i]为P[i]的前缀和，sum1[i]为将前i个点的所有物品全部放在第i个位置的花费，那么，sum1[i]=sum[i-1]*(x[i]-x[i-1])+sum1[i-1];
f[i]表示在第i个位置建立仓库的最小花费，f[i]=min{f[j]+sum1[i]-sum1[j]-sum[j]*(x[i]-x[j])+c[i]};
那么我们化简整理一下，f[i]-sum1[i]-c[i]=-sum[j]*x[i]+f[j]-sum1[j]+sum[j]*x[j];
那么，我们令Y(i,j)=f[i]-sum1[i]-c[i],K(j)=-sum[j],B(j)=f[j]-sum1[j]+sum[j]*x[j];
那么，K(j)单调递减，x[i]单调递增，那么维护队尾信息时，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率大于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)>Y(h+1)那么弹出。
附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 1000005
#define ll long long
#define K(x) (-sum[x])
#define B(x) (f[x]+dis[x]*sum[x]-sum1[x])
#define Y(x,y) ((K(y)*dis[x])+B(y))
ll f[N],sum[N],dis[N],sum1[N],c[N];
int q[N],n;
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld%lld%lld",&dis[i],&x,&c[i]);
sum[i]=sum[i-1]+x;
sum1[i]=sum1[i-1]+sum[i-1]*(dis[i]-dis[i-1]);
}
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h])>=Y(i,q[h+1]))h++;
f[i]=Y(i,q[h])+sum1[i]+c[i];
while(h<t&&cmp(i,q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld
",f[n]);
return 0;
}
（4）小P的牧场（斜率优化常见题）
和上一题几乎一样，状态和转移基本没有变化，只是x[i]变成了i，其他的没有变化
直接附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 1000005
#define ll long long
#define K(x) (-sum[x])
#define B(x) (f[x]+x*sum[x]-sum1[x])
#define Y(x,y) ((K(y)*x)+B(y))
ll f[N],sum[N],sum1[N],c[N];
int q[N],n;
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
sum1[i]=sum1[i-1]+sum[i-1];
}
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h])>=Y(i,q[h+1]))h++;
f[i]=Y(i,q[h])+sum1[i]+c[i];
while(h<t&&cmp(i,q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld
",f[n]);
return 0;
}
（5）防御准备（斜率优化常见题）
和上一题几乎一样，比上一题更简单一点，就是将sum[i]变成i...
没什么好说的...附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 1000005
#define ll long long
#define K(x) (-x)
#define B(x) (f[x]+1ll*x*x-sum1[x])
#define Y(x,y) ((1ll*K(y)*x)+B(y))
ll f[N],sum1[N],c[N];
int q[N],n;
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
for(int i=1;i<=n;i++)
{
sum1[i]=sum1[i-1]+i-1;
}
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h])>=Y(i,q[h+1]))h++;
f[i]=Y(i,q[h])+sum1[i]+c[i];
while(h<t&&cmp(i,q[t-1],q[t]))t--;
q[++t]=i;
}
printf("%lld
",f[n]);
return 0;
}
（6）Apio2014 序列分割
这个DP方程很简单，但是需要知道一件事...就是切的顺序和答案无关...
证明：（sum[i]是a[i]的前缀和）
设：在i,j(j>i)位置切割。
那么如果先切i，则：ans=sum[i]*(sum[n]-sum[i])+(sum[j]-sum[i])*(sum[n]-sum[j]) ;
展开：ans=sum[i]*sum[n]-sum[i]^2+sum[j]*sum[n]-sum[j]^2-sum[i]*sum[n]+sum[i]*sum[j];
整理：ans=-sum[i]^2+sum[j]*sum[n]-sum[i]*sum[n]+sum[i]*sum[j]-sum[j]^2;
再整理：ans=sum[j]*(sum[n]-sum[j])+sum[i]*(sum[j]-sum[i]);仔细观察发现，这就是先切j的答案。
因此，切割顺序与答案无关。
那么DP方程显而易见：f[i][k]表示前i个节点，切k次的最大价值并且，在第i个节点处切一次
转移：f[i][k]=max{f[j][k-1]+(sum[i]-sum[j])*(sum[n]-sum[i])};
但是这样不能斜率优化，我们考虑将k这一维移到外面
即：f[k][i]=max{f[k-1][j]+(sum[i]-sum[j])*(sum[n]-sum[i])};
这样可以发现，k只与k-1相关，我们可以通过滚动数组优化一维，省些空间，其实并不一定需要，但是这样看起来方便，写到这一步就可以展开优化了。
即：f[i]=max{g[j]+(sum[i]-sum[j])*(sum[n]-sum[i])};
整理：f[i]+sum[i]*sum[i]=sum[i]*sum[j]+g[j]+sum[i]*sum[n]-sum[j]*sum[n];
Y(i,j)=f[i]+sum[i]*sum[i];K(j)=sum[j];B(j)=g[j]+sum[i]*sum[n]-sum[j]*sum[n];
那么我们可以通过斜率优化完成，K(j)单调递增，x(i)单调递增，这样维护队尾信息的时候，如果(t-1,B(t-1))与(i,B(i))构成直线的斜率小于(t,B(t))与(i,B(i))构成直线的斜率，弹出t。维护队首信息时，如果Y(h)<Y(h+1)那么弹出。
附上代码：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 100005
#define ll long long
#define K(x) (sum[x])
#define B(x) (g[x]-sum[x]*sum[x])
#define Y(x,y) (K(y)*sum[x]+B(y))
ll g[N],f[N],sum[N];
int n,k,que[N];
bool cmp(int i,int j,int k)
{
ll x=(K(i)-K(k))*(B(j)-B(i));
ll y=(K(i)-K(j))*(B(k)-B(i));
return x>=y;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-1]+x;
}
for(int i=1;i<=k;i++)
{
int h=0,t=0;
for(int j=i;j<=n;j++)
{
while(h<t&&Y(j,que[h])<Y(j,que[h+1]))h++;
f[j]=Y(j,que[h]);
while(h<t&&cmp(j,que[t-1],que[t]))t--;
que[++t]=j;
}
for(int j=i;j<=n;j++)g[j]=f[j];
}
printf("%lld
",f[n]);
return 0;
}
（7）Sdoi2016 征途
方差是啥？百度百科：https://baike.baidu.com/item/%E6%96%B9%E5%B7%AE
接下来就是数学能力了...
orz orz fcwww http://www.cnblogs.com/suika/p/9021575.html
附上代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
#define N 3005
#define ll long long
#define K(x) (-2ll*sum[x])
#define B(x,z) (f[x][z]+sum[x]*sum[x]*m)
#define Y(x,y,z) ((K(y)*m*sum[x])+B(y,z))
ll f[N][N],sum[N];
int q[N],n,m;
bool cmp(int i,int j,int k,int z)
{
ll x=(K(i)-K(k))*(B(j,z)-B(i,z));
ll y=(K(i)-K(j))*(B(k,z)-B(i,z));
return x>=y;
}
int main()
{
for(int i=0;i<N;i++)for(int j=0;j<N;j++)f[i][j]=1ll<<60;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
}
f[0][0]=0;
for(int j=1;j<=m;j++)
{
int h=0,t=0;
for(int i=1;i<=n;i++)
{
while(h<t&&Y(i,q[h],j-1)>=Y(i,q[h+1],j-1))h++;
f[i][j]=Y(i,q[h],j-1)+sum[i]*sum[i]*m;
//printf("%d %d %lld
",i,j,f[i][j]);
while(h<t&&cmp(i,q[t-1],q[t],j-1))t--;
q[++t]=i;
}
}
printf("%lld
",f[n][m]-sum[n]*sum[n]);
return 0;
}