斜率DP题目小结

如果K是常数：单调队列

如果X单调，K单调：斜率优化

若K不单调，X单调：二分在（上）下凸壳上寻找斜率作为dp值。 

题目1：华工G：https://www.nowcoder.com/acm/contest/94/G

DP方程：

题解：X单调，K不单调，斜率优化+二分：二分找k作为答案

代码：https://www.nowcoder.com/acm/contest/view-submission?submissionId=25108586

题目2：BZOJ1010：https://www.lydsy.com/JudgeOnline/problem.php?id=1010

DP方程：

,（Y X里面的i应该写成j）

题解：X单调，K单调，斜率优化：

理解与记忆：

出队：斜率式比较:假设j>k,j比k优则有....的那条式子.不断head+1与head比较，得到一个合适的dp(i)值

入队：用斜率逼近来记忆，维护下凸包：判断Ktail tail-1>Ktail i说明K=g(i)逼近时不会碰到tail，不断去尾，最后i入队

模板代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=50005;
ll s[maxn];int q[maxn];ll dp[maxn];ll g[maxn];
int n; ll l;
inline ll Y(int i,int j){return (dp[i]+g[i]*g[i]+2*g[i]*(l+1))-(dp[j]+g[j]*g[j]+2*g[j]*(l+1));}
inline ll X(int i,int j){return (g[i]-g[j])*2;}
inline ll f(int i,int j){return dp[j]+(g[i]-g[j]-l-1)*(g[i]-g[j]-l-1);}
int main()
{
	scanf("%d %lld",&n,&l);ll t=0;int head=0,tail=0;
	memset(dp,0,sizeof(dp));memset(q,0,sizeof(q));memset(s,0,sizeof(s));
	for(int i=1;i<=n;i++)scanf("%lld",&t),s[i]=s[i-1]+t,g[i]=s[i]+i;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&Y(q[head+1],q[head])<=g[i]*X(q[head+1],q[head]))head++;
		dp[i]=f(i,q[head]);
		while(head<tail&&Y(i,q[tail])*X(q[tail],q[tail-1])<=Y(q[tail],q[tail-1])*X(i,q[tail])  )tail--;
		q[++tail]=i;
	}	
	printf("%lld\n",dp[n]);
} 

题目3：hdu3045:http://acm.hdu.edu.cn/showproblem.php?pid=3045,区间长度不少于m,同POJ3709

DP方程：

题解：x单调，k单调，斜率优化+延迟加入走起

延迟加入的理解：求出dp(j)之后，dp(j)只对dp(j+m),dp(j+m+1)...以后的状态起决策作用

举个例子：求dp(10),m=3  那么决策应该从dp1~dp7选min  

求出dp10之后，才入队dp8,因为dp(11)会用到dp(8),

那什么时候才开始入队呢？i>=2m-1的时候，n=5,m=3理解一下

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=400005;
ll s[maxn];int q[maxn];ll dp[maxn];ll a[maxn];
int n; int m;
inline ll Y(ll i,ll j){return (dp[i]-s[i]+i*a[i+1])-(dp[j]-s[j]+j*a[j+1]);}
inline ll X(ll i,ll j){return (a[i+1]-a[j+1]);}
inline ll f(ll i,ll j){return dp[j]+s[i]-s[j]-a[j+1]*(i-j);}
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		memset(dp,0,sizeof(dp));	memset(q,0,sizeof(q));	memset(s,0,sizeof(s));
		for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
		sort(a+1,a+1+n);
		for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
		int head=0,tail=1;
		for(int i=1;i<=n;i++)
		{
			while(head<tail&&Y(q[head+1],q[head])<=1ll*i*X(q[head+1],q[head]))head++;
			dp[i]=f(i,q[head]);
			int late=i-m+1;
			if(i>=2*m-1)
			{
				while(head<tail&&Y(late,q[tail])*X(q[tail],q[tail-1])<=Y(q[tail],q[tail-1])*X(late,q[tail])  )tail--;
				q[++tail]=late;
			}
		}	
		printf("%I64d\n",dp[n]);
	}
} 

题目4：hdu3507:http://acm.hdu.edu.cn/showproblem.php?pid=3507

DP方程:,m是常数

题解：直接斜率优化搞，跟题目2一样

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500005;
ll s[maxn];int q[maxn];ll dp[maxn];
int n,m;
inline ll Y(int i,int j){return dp[i]+s[i]*s[i]-dp[j]-s[j]*s[j];}
inline ll X(int i,int j){return 2*(s[i]-s[j]);}
inline ll f(int i,int j){return dp[j]+m+(s[i]-s[j])*(s[i]-s[j]);}
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		ll t=0;int head=0,tail=0;
		memset(dp,0,sizeof(dp));	memset(q,0,sizeof(q));	memset(s,0,sizeof(s));
		for(int i=1;i<=n;i++)scanf("%I64d",&t),s[i]=s[i-1]+t;
		for(int i=1;i<=n;i++)
		{
			while(head<tail&&Y(q[head+1],q[head])<=s[i]*X(q[head+1],q[head]))head++;
			dp[i]=f(i,q[head]);
			while(head<tail&&Y(i,q[tail])*X(q[tail],q[tail-1])<=Y(q[tail],q[tail-1])*X(i,q[tail])  )tail--;
			q[++tail]=i;
		}	
		printf("%I64d\n",dp[n]);
	}	
} 

题目5：BZOJ4518：https://www.lydsy.com/JudgeOnline/problem.php?id=4518

DP方程：前j条路分成i段：

题解：X单调，K单调，斜率优化走起，不过这次是二维，注意写法

对每个i跑一遍斜率优化得出dp i j 即可，注意边界！

代码：

//WA 点 初始化的锅dp[0][0]=0;其余为inf 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3005;
ll a[maxn];ll s[maxn];ll dp[maxn][maxn];ll q[maxn];
inline ll Y(int i,int j,int k){return (dp[i-1][j]+s[j]*s[j])-(dp[i-1][k]+s[k]*s[k]);}
inline ll X(int j,int k){return 1ll*2*(s[j]-s[k]);}
inline ll f(int i,int j,int k){return dp[i-1][k]+(s[j]-s[k])*(s[j]-s[k]);}
int main()
{
	ll n,m;
	scanf("%lld %lld",&n,&m);s[0]=0;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
	for(int i=0;i<=m;i++)for(int j=0;j<=n;j++)dp[i][j]=1000000000000000000;
	dp[0][0]=0;
	for(int i=1;i<=m;i++)
	{
		//memset(q,0,sizeof(q));
		int head=0;int tail=0;
		for(int j=1;j<=n;j++)
		{
			while(head<tail&&Y(i,q[head+1],q[head])<=X(q[head+1],q[head])*s[j])head++;
			dp[i][j]=f(i,j,q[head]);
			while(head<tail&&Y(i,j,q[tail])*X(q[tail],q[tail-1])<=X(j,q[tail])*Y(i,q[tail],q[tail-1]))tail--;
			q[++tail]=j;
		}
	}
	printf("%lld\n",m*dp[m][n]-s[n]*s[n]);	
}

滚动数组的写法：

//WA 点 初始化的锅dp[0][0]=0;其余为inf 
//入队注释那里，乘法貌似溢出了QAQ ull都WA得换成除法才能AC
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3005;
ll a[maxn];
ll s[maxn];
ll dp[2][maxn];
ll q[maxn];
inline ll Y(int i,int j,int k){return (dp[i^1][j]+s[j]*s[j])-(dp[i^1][k]+s[k]*s[k]);}
inline ll X(int j,int k){return 1ll*(s[j]-s[k]);}
inline ll f(int i,int j,int k){return dp[i^1][k]+(s[j]-s[k])*(s[j]-s[k]);}
int main()
{
	ll n,m;
	scanf("%lld %lld",&n,&m);s[0]=0;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
	for(int i=0;i<=1;i++)for(int j=0;j<=n;j++)dp[i][j]=2000000000000000000;
	dp[0][0]=0;
	for(int i=1,t=1;i<=m;t^=1,i++)
	{
		//memset(q,0,sizeof(q));
		int head=0;int tail=0;
		for(int j=1;j<=n;j++)
		{
			while(head<tail&&Y(t,q[head+1],q[head])<=X(q[head+1],q[head])*s[j]*2)head++;
			dp[t][j]=f(t,j,q[head]);
			//while(head<tail && (unsigned long long)Y(t,j,q[tail])*(unsigned long long)X(q[tail],q[tail-1])<=(unsigned long long)X(j,q[tail])*(unsigned long long)Y(t,q[tail],q[tail-1]) )tail--;
			while(head<tail && (double)Y(t,j,q[tail])/(double)X(j,q[tail])<=(double)Y(t,q[tail],q[tail-1])/(double)X(q[tail],q[tail-1] ))tail--;
			q[++tail]=j;
		}
	}
	printf("%lld\n",m*dp[m&1][n]-s[n]*s[n]);	
}