斜率优化复习记

由于我最近又脑残到了一定程度。所以滚回来复习一发斜率优化。

大体经过是这个样子的。9.17晚上，打开DP优化PPT。斜率优化！我学过啊，随便推推吧。

。。。一晚上过去了。。。

cnm我是不是学了假的斜率优化。

9.18耽搁了一天。9.19重新开开了这个题。然后上午收到了ACM区域赛过了的消息激动了一发。然后一直拖到下午才搞定这个题。

——————————————————分个鸽——————————————————

先扔链接。https://www.lydsy.com/JudgeOnline/problem.php?id=3156

由于我太蠢。最开始设的状态是 $f_i_,_0$ 表示第 $i$ 个位置不放塔的最小代价， $f_i_,_1$ 表示放塔。然后我们倒序做。起始状态 $f_n_,_1=A_n$ 。

转移非常蠢。不写了。然后我们发现其实第二维并没有用。我们直接用 $f_i$ 表示第 $i$ 个位置强制放塔，然后过程中取答案即可。

转移就是 $f_i=min(f_j+sum_i_+_1-sum_j-(j-i-1)*dis_j)$ 其中 $dis_i=n-i$ 就是i到n的距离 $sum_i=sum_{j=i}^ndis_j$ 就是后缀和

然后就到了我们喜闻乐见的斜率优化了。

我来大体描述一下~~十分玄学的~~斜率优化。

一般来说它的状态转移是这个样子 $F_i =min /max(F_j+p_i*q_j)$

它大体可以转换成这种形式 $F_i+p_i*q_j=Fj$ （当然左右都可以有一些常数[已知项]）

是不是看起来很熟悉！！ $b+kx=y$ 是不是！！！我们就把求 $F_i$ 变成了求截距的极值！！！

非常优秀对不对。但是分析起来贼难受。

以这个题为例。

化简一下式子： $f_i=f_j+sum_{i+1}-sum_j-dis_j*j+dis_j*i+dis_j$

$f_i-sum_{i+1}-dis_j*i=f_j-sum_j-dis_j*j+dis_j$

我们设 $i<j<k$

设 $f_j+sum_{i+1}-sum_j-(j-i-1)*dis_j<f_k+sum_{i+1}-sum_k-(k-i-1)*dis_k$

然后移项得到 $f_j-sum_j-j*dis_j+dis_j-f_k+sum_k-k*dis_k-dis_k<i*(dis_k-dis_j)$

由于我们设的 $j<k$ 所以 $dis_k-dis_j<0$ 我们把它移到左边得到 $(Y_j-Y_k)/(dis_j-dis_k)>-i$ Y就是那一大坨。

至于为什么是 $-i$ 是因为我们用 $(Y_j-Y_k)/(dis_j-dis_k)$ 表示斜率很方便。

我们利用队列维护这个斜率。当队首不够优的时候我们就弹出队首。也就是 $(Y_j-Y_k)/(dis_j-dis_k)<-i$ 的时候弹出。

接下来是队尾的处理。我们设 $j<k<l$ 然后用 $g(k,j)$ 表示 $j$ 到 $k$ 的斜率，设 $g(l,k)>g(k,j)$ 。我们进行分类讨论。如果 $g(l,k)<F_i$ 那么很明显我们选 $l$ 最优。如果 $g(l,k)>F_i$ 我们有 $k$ 优于 $l$ 但是 $j$ 又优于 $k$ 。所以我们得出我们维护的是上凸壳。用斜率将不合法的队尾弹出即可。

所以搞定啦QwQ。很奇怪对不对...~~我也这么觉得~~

——————————————————分个鸽——————————————————

我再整理一下另一种理解方式。

我们观察直线的变化特点。 $k=-i$ 所以 $k$ 随 $i$ 的增加而递减，所以我们可以得到我们维护的是上凸壳。

同理可以得到上面的结论。

——————————————————分个鸽——————————————————

一些容易错的地方...

在推式子之前一定要分析好 $i,j,k$ 的大小关系，不要像我一样蠢...导致不等式除负数没变号然后GG。然后维护的时候记得凸壳上必须留着一个点...不然也会GG...还有就是斜率优化第一步的状态转移方程一定要列对...我经常先不写细节先推完式子再补细节...然后就非常容易符号出错...

好了没啥了留下代码我就跑路了。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 1000010
#define db double
#define inf 20021225ll
#define ll long long
using namespace std;
ll f[maxn],sum[maxn],dis[maxn],ans=inf*inf;
int que[maxn],hd,tl,a[maxn];
db calc(int x)
{
	return (db)f[x]-sum[x]-x*dis[x]+dis[x];
}
db slope(int j,int k)
{
	//printf("%lf %lf %lf
",calc(j),calc(k),(double)dis[j]-dis[k]);
	return (calc(j)-calc(k))/((db)dis[j]-dis[k]);
}
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(i=n;i;i--)	dis[i]=n-i,sum[i]=sum[i+1]+dis[i];
	f[n]=a[n];que[1]=n;hd=tl=1;ans=min(ans,f[n]+sum[1]);sum[0]=sum[1];
	for(i=n-1;i;i--)
	{
		while(hd<tl&&-slope(que[hd],que[hd+1])>i)	hd++;
		//printf("%d %d %lf ",hd,tl,slope(que[hd],que[hd+1]));
		j=que[hd];
		f[i]=f[j]+sum[i+1]-sum[j]-dis[j]*(j-i-1)+a[i];
		ans=min(ans,f[i]+sum[1]-sum[i]-dis[i]*(i-1));
		//printf("%d %d %lld %lld
",i,j,f[i],f[i]+sum[1]-sum[i]-dis[i]*(i-1));
		while(hd<tl&&slope(que[tl],i)<slope(que[tl-1],que[tl]))	tl--;
		que[++tl]=i;
	}
	printf("%lld
",ans);
	return 0;
}