斜率优化dp

是一种可以针对i j具有某种单调性来用斜率优化$dp\{dp\}$转移的一种方式.

例:BZOJ1010 玩具装箱toy

很容易的写出$dpdp$方程,令$f_{i}f\_i$表示解决前$ii$个的最小花费.

那么转移也很明显就是:$f_i=f_j+(su{m}_i-su{m}_j-L+i-j-1{)}^{2}f\_i=f\_j+(sum\_i-sum\_j-L+i-j-1)^2$.

很显然复杂度是$n^{2}n^2$的,如何优化呢.

斜率优化第一步假如是一次函数或许可以直接分析$i,ji,j$得到单调性.但是这个是二次函数,二次函数可以分析前面两个的关系分析出单调性,比如说设,令$f_{i}f\_i$在决策点$kk$的转移更优,得到一组不等式.

首先把$su{m}_i+i-L-1\{sum\_i+i-L-1\}$设置成$AA$.然后把$su{m}_j+jsum\_j+j$设置成$BB$.

那么不等式就变成了:.

进一步化简可以得到:

到这时已经是一个斜率公式了.由$AA$的定义来说$AA$是递增的,对于$j,kj,k$来说它们两点连线的斜率假如大于$2\ast A2*A$,那么$kk$一定是会被淘汰的.答案最优解显然就是第一个大于斜率的$jj$.显然斜率$2\ast A2*A$是递增的,因为$AA$是递增的.当加入一个点$ll$,当它与队尾的斜率小于队尾与前面的斜率时,队尾就可以pop了.因为前面的推论.考虑当前k与前一个构成的一定是小于$2\ast A2*A$的.不优且影响单调性.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e4+5;
const int mod=998244353;
const double eps=1e-9;

int c[N];
ll sum[N],f[N];
int n,l;
int q[N],L=0,R=0;
double A(int u)
{
	return sum[u]+u-l-1;
}

double B(int u)
{
	return sum[u]+u;
}

double solve(int a,int b)
{
	return (double)(f[a]+B(a)*B(a)-f[b]-B(b)*B(b))/(double)(B(a)-B(b));
}

void solve()
{
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		sum[i]=sum[i-1]+c[i];
	}sum[0]=f[0]=0;
	for(int i=1;i<=n;i++)
	{
		while(L<R&&solve(q[L+1],q[L])<=2*A(i))	L++;
		int j=q[L];
		f[i]=f[j]+(sum[i]-sum[j]-l+i-j-1)*(sum[i]-sum[j]-l+i-j-1);
		while(L<R&&solve(q[R],q[R-1])>solve(i,q[R]))	R--;
		q[++R]=i;
	}
	printf("%lld\n",f[n]);
}

int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	solve();
	return 0;
}

有个细节必须队列开始必须$L=RL=R$,不是只有队列里面有两个元素才能判断斜率转移,事实队列里一个元素和前一个元素也要判断转移.