斜率DP

2020-03-07

字数统计: 2.1k字 | 阅读时长≈ 11分钟

斜率DP的总结

斜率DP用来优化一类形如 dp[i]=min(dp[j]+f(i,j))dp[i]=min(dp[j]+f(i,j)) 的动态规划问题

从HDU3507入手

将长度为 nn 的数组划分成若干段，每段的花费为这段数字和的平方加 MM,求最小花费。

定义 dp[i]dp[i] 为到i为止划分为若干段的最小花费，则有转移方程：

dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}(j<=i)dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}(j<=i)

可以发现复杂度为n2n2的。

设 k<j<ik<j<i
若 jj 转移至 ii 比 kk 转移至 ii 更优(本题中为 jj 转移至 ii 花费更小)
则有 dp[j]+M+(sum[i]−sum[j])2<dp[k]+M+(sum[i]−sum[k])2dp[j]+M+(sum[i]−sum[j])2<dp[k]+M+(sum[i]−sum[k])2
移项化简得 (dp[j]+sum[j]2)−(dp[k]+sum[k]2)2sum[j]−2sum[k]<sumi−(dp[k]+sum[k]2)2sum[j]−2sum[k]<sum[i]
设Y(x)=dp[x]+sum[x]2Y(x)=dp[x]+sum[x]2,X(x)=2sum[x]X(x)=2sum[x],g[i,j]=Y(i)−Y(j)X(i)−X(j)g[i,j]=Y(i)−Y(j)X(i)−X(j)
则有当g[j,k]<sum[i]g[j,k]<sum[i]时，jj转移至ii要比kk转移至ii更优
分析当g[i,j]<g[j,k]g[i,j]<g[j,k]时，若g[i,j]<sum[i]g[i,j]<sum[i],则ii比jj优，若g[i,j]>=sum[i]g[i,j]>=sum[i],则g[j,k]>sum[i]g[j,k]>sum[i]，即jj不如kk优
结论:对于ii点当g[j,k]<g[i,j]g[j,k]<g[i,j]时，jj必然不是最优的转移方案
用单调队列维护有效解集，则有效解集的斜率为递增的

1	复制#include <bits/stdc++.h>
2	using namespace std;
3	#define ll long long
4	#define go(i,a,b) for(ll i=(a);i<=(b);i++)
5	#define N 500005
6	#define p2(x) (x)*(x)
7	ll a[N],dp[N],n,m,head,tail,q[N],sum[N];
8	ll getdp(ll i,ll j){return dp[j]+m+p2(sum[i]-sum[j]);}
9	ll getup(ll i,ll j){return dp[i]+p2(sum[i])-(dp[j]+p2(sum[j]));}
10	ll getdown(ll i,ll j){return 2ll*(sum[i]-sum[j]);}
11	void init(){
12	head=tail=dp[0]=sum[0]=0;
13	q[tail++]=0;
14	}
15	int main()
16	{
17	while(cin>>n>>m){
18	go(i,1,n)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
19	init();
20	go(i,1,n){
21	while(head+1<tail&&getup(q[head],q[head+1])>sum[i]*getdown(q[head],q[head]+1))head++;
22	dp[i]=getdp(i,q[head]);
23	while(head+1<tail&&getdown(q[tail-1],q[tail-2])getup(i,q[tail-1])<=getdown(i,q[tail-1])getup(q[tail-1],q[tail-2]))tail--;
24	q[tail++]=i;
25	}
26	printf("%lld\n",dp[n]);
27	}
28	return 0;
29	}

dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}(j<=i)dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}(j<=i)+斜率优化，入门题

1	复制#include <bits/stdc++.h>
2	using namespace std;
3	#define ll long long
4	#define go(i,a,b) for(ll i=(a);i<=(b);i++)
5	#define N 500005
6	#define p2(x) (x)*(x)
7	ll a[N],dp[N],n,m,head,tail,q[N],sum[N];
8	ll getdp(ll i,ll j){return dp[j]+m+p2(sum[i]-sum[j]);}
9	ll getup(ll i,ll j){return dp[i]+p2(sum[i])-(dp[j]+p2(sum[j]));}
10	ll getdown(ll i,ll j){return 2ll*(sum[i]-sum[j]);}
11	void init(){
12	head=tail=dp[0]=sum[0]=0;
13	q[tail++]=0;
14	}
15	int main()
16	{
17	while(cin>>n>>m){
18	go(i,1,n)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
19	init();
20	go(i,1,n){
21	while(head+1<tail&&getup(q[head],q[head+1])>sum[i]*getdown(q[head],q[head]+1))head++;
22	dp[i]=getdp(i,q[head]);
23	while(head+1<tail&&getdown(q[tail-1],q[tail-2])getup(i,q[tail-1])<=getdown(i,q[tail-1])getup(q[tail-1],q[tail-2]))tail--;
24	q[tail++]=i;
25	}
26	printf("%lld\n",dp[n]);
27	}
28	return 0;
29	}

dp[i]=min{dp[j]+(sum[i]−sum[j]+i−j−1−L)2}dp[i]=min{dp[j]+(sum[i]−sum[j]+i−j−1−L)2}，思路为将括号里的内容分为两个函数，便于展开。打错了函数名，调了一上午。。。

1	复制#include <bits/stdc++.h>
2	using namespace std;
3	#define ll long long
4	#define go(i,a,b) for(ll i=(a);i<=(b);i++)
5	#define N 500005
6	#define p2(x) (x)*(x)
7	ll a[N],sum[N],tail,head,q[N],L,n,m,dp[N];
8	void init(){head=tail=sum[0]=dp[0]=0;q[tail++]=0;}
9	ll getx(ll x){return x+sum[x];}
10	ll gety(ll x){return x+sum[x]+1+L;}
11	ll getdp(ll i,ll j){return dp[j]+p2(getx(i)-gety(j));}
12	ll getup(ll j,ll k){return (dp[j]+p2(gety(j)))-(dp[k]+p2(gety(k)));}
13	ll getdown(ll j,ll k){return 2ll*(gety(j)-gety(k));}
14	int main()
15	{
16	cin>>n>>L;
17	init();
18	go(i,1,n)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
19	go(i,1,n){
20	while(head+1<tail&&getup(q[head+1],q[head])<getx(i)*getdown(q[head+1],q[head]))head++;
21	dp[i]=getdp(i,q[head]);
22	while(head+1<tail&&getup(i,q[tail-1])getdown(q[tail-1],q[tail-2])<getup(q[tail-1],q[tail-2])getdown(i,q[tail-1]))tail--;
23	q[tail++]=i;
24	}
25	printf("%lld\n",dp[n]);
26	return 0;
27	}

给定n块木板长与高，要求分为k组，每组经过切割变为等高，切割部分不能再利用，求最小浪费面积

dp[k][i]=maxdp[k−1][j]+h[j]∗(sum[i]−sum[j])dp[k][i]=maxdp[k−1][j]+h[j]∗(sum[i]−sum[j])

1	复制#include <bits/stdc++.h>
2	using namespace std;
3	#define ll long long
4	#define go(i,a,b) for(ll i=(a);i<=(b);i++)
5	#define N 5005
6	#define lll __int128
7	#define p2(x) (x)*(x)
8	struct node{
9	ll a,b;
10	bool operator<(const node &x)const{
11	return a>x.a;
12	}
13	}s[N];
14	ll dp[N][N],sum[N],head[N],tail[N],q[N][N],n,m;
15	ll getdp(ll i,ll j,ll y){return dp[y-1][j]+s[i].a*(sum[i]-sum[j]);}
16	ll gety(ll i,ll y){return (dp[y-1][i]);}
17	ll getup(ll j,ll k,ll y){return gety(j,y)-gety(k,y);}
18	ll getdown(ll j,ll k){return sum[j]-sum[k];}
19	ll getx(ll i){return s[i].a;}
20	int main()
21	{
22	scanf("%lld%lld",&n,&m);ll sum1=0;
23	go(i,1,n)scanf("%lld%lld",&s[i].b,&s[i].a),sum1+=s[i].b*s[i].a;
24	sort(s+1,s+1+n);
25	go(i,1,n)sum[i]=sum[i-1]+s[i].b;
26	go(i,0,m-1)head[i]=tail[i]=0,q[i][tail[i]++]=0;
27	go(j,1,m){
28	go(i,1,n){
29	while(head[j-1]+1<tail[j-1]&&
30	(lll)getup(q[j-1][head[j-1]+1],q[j-1][head[j-1]],j)
31	>(lll)getx(i)*(lll)getdown(q[j-1][head[j-1]+1],q[j-1][head[j-1]]))
32	head[j-1]++;
33	dp[j][i]=getdp(i,q[j-1][head[j-1]],j);
34	while(head[j]+1<tail[j]&&
35	(lll)getup(i,q[j][tail[j]-1],j+1)
36	*(lll)getdown(q[j][tail[j]-1],q[j][tail[j]-2])
37	>(lll)getup(q[j][tail[j]-1],q[j][tail[j]-2],j+1)
38	*(lll)getdown(i,q[j][tail[j]-1]))tail[j]--;
39	q[j][tail[j]++]=i;
40	}
41	}
42	printf("%lld\n",sum1-dp[m][n]);
43	return 0;
44	}