关于斜率优化
|
680
|
0
|
学习笔记

1080 字
|
5 分钟

前言

其实这篇文章早就想写了，只不过一直咕咕咕着，咕了一年（大雾。

现在对于斜率优化已经产生了十分深刻的李姐了，所以可以放心大胆地胡扯了。

正文

关于一个$DP$方程，如果它的形式如$F[i]=max(or min)(F[j]+(一堆只关于j的式子)+(一堆只关于i的式子))$那么这样我们是可以对其进行单调队列优化的，把复杂度降低一维。但是如果形式如$F[i]=max(or min)(F[j]+(一堆只关于j的式子)*(一堆只关于i的式子))$那么这样显然就不可以用单调队列优化了，因为仅仅维护$F[j]$最优不可能保证全局最优，仅仅维护$(一堆只关于j的式子)$最优也不可以保证全局最优。那么这个时候就要使用斜率优化了。

我们设当前$F[i]$通过$F[j1]$和$F[j2]$推来 $(j1<=j2)$

我们试图比较这两个$j$通过哪个推来更优。

但是这样貌似很麻烦，所以我们假设$F[j2]$推来比$F[j1]$更优 ，然后试图找到使得$F[j2]$推来比$F[j1]$更优的充要条件。

以[CEOI2004]锯木厂选址为例，下面给出暴力$N^2$DP代码，洛谷上满分，LOJ$40$。

#include<bits/stdc++.h>
#define LL long long
#define Maxn 20005
using namespace std;
LL n,w[Maxn],d[Maxn],F[Maxn][3],SumT[Maxn],SumW[Maxn];
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
int main()
{
	read(n);
	for (int i=1;i<=n;i++) read(w[i]),read(d[i]);
	for (int i=n;i>=1;i--) d[i]+=d[i+1],SumT[i]=d[i]*w[i]+SumT[i+1],SumW[i]=w[i]+SumW[i+1];
	for (int i=1;i<=n-1;i++) F[i][1]=SumT[1]-SumT[i]-d[i]*(SumW[1]-SumW[i]);
	LL answer=2e9;
	for (int i=2;i<=n;i++)
	{
		F[i][2]=2e9;
		for (int j=1;j<i;j++)
		F[i][2]=min(F[i][2],F[j][1]+SumT[j+1]-SumT[i]-d[i]*(SumW[j+1]-SumW[i]));	
		answer=min(answer,F[i][2]+SumT[i+1]);
	} 
	cout<<answer<<endl;
	return 0;
}

（以上暂时不用读者理解DP转移的意思，仅仅只是列出形式而已，当然如果理解更嘉）

我们提取出关键转移语句$F[i][2]=min(F[i][2],F[j][1]+SumT[j+1]-SumT[i]-d[i]*(SumW[j+1]-SumW[i]));$

然后开始斜率优化

设$j1<=j2$因为是$min$所以$j2$比$j1$优显然是比它小

$F[j1][1]+SumT[j1+1]-SumT[i]-d[i]*(SumW[j1+1]-SumW[i])>=F[j2][1]+SumT[j2+1]-SumT[i]-d[i]*(SumW[j2+1]-SumW[i])$

移项并消掉两边相同项(也就是只关于$i$的项)

$F[j1][1]+SumT[j1+1]-d[i]*SumW[j1+1]>=F[j2][1]+SumT[j2+1]-d[i]*SumW[j2+1]$

然后将关于$j1,j2$的项移到一边，关于$i和j1,j2$的项移到另一边。

$F[j1][1]+SumT[j1+1]-F[j2][1]-SumT[j2+1]>=d[i]*(SumW[j1+1]-SumW[j2+1])$

然后把$i和j1,j2$那一边的$j1,j2$部分除过去，记得判断会不会除负数(我这里$SumW$是后缀和且单位元素不为负，所以$SumW[j1+1]-SumW[j2+1]定>0$)

$(F[j1][1]+SumT[j1+1]-F[j2][1]-SumT[j2+1])/(SumW[j1+1]-SumW[j2+1])>=d[i]$

这就是$j2$推来比$j1$优的充要条件。(也对应着斜率优化的$pop$队首)

那么我们继续考虑有没有可能某个决策点一定不可能转移过来。

我们把$(F[j1][1]+SumT[j1+1]-F[j2][1]-SumT[j2+1])/(SumW[j1+1]-SumW[j2+1])$当成一段斜率$K(j1,j2)$，那么请看下图。

上图中$k(j,k)>k(i,j)$，如果$k(j,k)>=d[i]$则k一定比j这个决策点优，若$k(j,k)<d[i]$则$j$比$k$优，但是因为$k(i,j)<k(j,k)$所以$i$一定也比$j$优，则这个$j$是无论如何都不会被选中的。所以我们需要在新的决策点入队时维护一个斜率单调不升的决策队列。（也可能是单调不降，需要看题目，由上面转移方程不等号的方向而定，分类讨论即可）(也对应着斜率优化的$pop$队尾)

如此我们便可以得出优化后的$dp$了

#include<bits/stdc++.h>
#define LL long long
#define Maxn 200005
using namespace std;
LL n,w[Maxn],d[Maxn],F[Maxn][3],SumT[Maxn],SumW[Maxn],q[Maxn],l,r;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
inline double slope(LL j1,LL j2){return (double)(F[j2][1]-F[j1][1]+SumT[j2+1]-SumT[j1+1])/(SumW[j2+1]-SumW[j1+1]);}
int main()
{
	read(n);
	for (int i=1;i<=n;i++) read(w[i]),read(d[i]);
	for (int i=n;i>=1;i--) d[i]+=d[i+1],SumT[i]=d[i]*w[i]+SumT[i+1],SumW[i]=w[i]+SumW[i+1];
	for (int i=1;i<=n-1;i++) F[i][1]=SumT[1]-SumT[i]-d[i]*(SumW[1]-SumW[i]);
	LL answer=1145141919810;
	r=q[++l]=1;
	for (int i=2;i<=n;i++)
	{
		while (l<r&&slope(q[l],q[l+1])>=d[i]) l++;
		F[i][2]=F[q[l]][1]+SumT[q[l]+1]-SumT[i]-d[i]*(SumW[q[l]+1]-SumW[i]);
		while (l<r&&slope(q[r-1],q[r])<slope(q[r],i)) r--;
		q[++r]=i;	
		answer=min(answer,F[i][2]+SumT[i+1]);
	} 
	cout<<answer<<endl;
	return 0;
}

比较有价值的题目

[JSOI2009]火星藏宝图

新的姿势，维护不同列的最值来代替$if$语句的判断区间位置。

暴力

#include<bits/stdc++.h>
#define LL long long
#define Maxn 200005 
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
struct island{LL x,y,v;}a[Maxn];
LL N,M,F[Maxn];
inline LL sqr(LL x){return x*x;}
inline bool cmp(island p,island q){if (p.x!=q.x) return p.x<q.x;return p.y<q.y;}
int main()
{
	read(N),read(M);
	for (int i=1;i<=N;i++) read(a[i].x),read(a[i].y),read(a[i].v);
	sort(a+1,a+N+1,cmp);
	F[1]=a[1].v;
	for (int i=2;i<=N;i++)
	{
		F[i]=-9999999999999;
		for (int j=1;j<i;j++)
		if (a[i].x>=a[j].x&&a[i].y>=a[j].y) F[i]=max(F[i],F[j]+a[i].v-sqr(a[i].x-a[j].x)-sqr(a[i].y-a[j].y));
	}
	cout<<F[N]<<endl;
	return 0;
}

优化代码

#include<bits/stdc++.h>
#define LL long long
#define Maxn 200005 
#define Maxm 1005 
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	x*=f;
}
struct island{LL x,y,v;}a[Maxn];
LL N,M,F[Maxn],q[Maxm][Maxn],l[Maxm],r[Maxm];
inline LL sqr(LL x){return x*x;}
inline bool cmp(island p,island q){if (p.y!=q.y) return p.y<q.y;return p.x<q.x;}
inline double slope(LL j1,LL j2){return (double)(F[j1]-F[j2]-a[j1].y*a[j1].y+a[j2].y*a[j2].y)/(a[j2].y-a[j1].y);	} 
int main()
{
	read(N),read(M);
	for (int i=1;i<=N;i++) read(a[i].x),read(a[i].y),read(a[i].v);
	sort(a+1,a+N+1,cmp);
	F[1]=a[1].v;
	q[1][++l[1]]=1;
	for (int i=2;i<=N;i++)
	{
		F[i]=-9999999999999;
		for (int j=1;j<=a[i].x;j++)
		{
			while (l[j]<r[j]&&slope(q[j][l[j]],q[j][l[j]+1])<=2*a[i].y) l[j]++;
			F[i]=max(F[i],F[q[j][l[j]]]+a[i].v-sqr(a[i].x-a[q[j][l[j]]].x)-sqr(a[i].y-a[q[j][l[j]]].y));
		} 
		while (l[a[i].x]<r[a[i].x]&&slope(q[a[i].x][r[a[i].x]-1],q[a[i].x][r[a[i].x]])>=slope(q[a[i].x][r[a[i].x]],i)) r[a[i].x]--;
		q[a[i].x][++r[a[i].x]]=i; 
	}
	cout<<F[N]<<endl;
	return 0;
}

摆渡车

泪目代码丢了，不过大力推荐。

征途

这题水极了，是模板题

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,a[3005],sum[3005],f[3005][3005],head,tail,q[3005];
double slope(LL x,LL y,LL z)
{
	return (double)(f[x][z]-f[y][z]+sum[x]*sum[x]-sum[y]*sum[y])/(sum[x]-sum[y]);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	memset(f,0x7f,sizeof(f));
	f[0][0]=0;
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],f[i][1]=sum[i]*sum[i]; 
	for (int k=2;k<=m;k++)
	{
		head=1;tail=0;
		q[++tail]=0;
		for (int i=1;i<=n;i++)
		{
			while (head<tail&&slope(q[head],q[head+1],k-1)<2*sum[i]) head++;
			f[i][k]=f[q[head]][k-1]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]);
			while (head<tail&&slope(q[tail-1],q[tail],k-1)>slope(q[tail],i,k-1)) tail--;
			q[++tail]=i;
		}
	} 
	cout<<m*f[n][m]-sum[n]*sum[n]<<endl;
	return 0;
}

学习小结斜率优化
暂无评论

发送评论 编辑评论 



























































































|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
 




颜文字
Emoji
小恐龙
花!
 


 














上一篇
下一篇