单调队列优化dp

前导:单调队列

知识什么的没有,不知道单调队列的话见上
不知道dp?
那我也没办法了..

顾名思义
我们总会碰到一些神奇的数据
比方说要求O(n)的题目
你只能推出O(n^2)
O(n^2)的题
你只有O(n^3)dp做法
异常尴尬
这时你可以看看有没有决策的循环
你可以考虑单调队列帮你达成题目的毒瘤数据要求
看看例题吧

例题1 琪露诺

我的第一道单调队列dp
朴素的dp应该还挺好推的

for(int i=l;i<=n;i++){
	for(int j=max(i-r,0);j<=i-l;j++)
		dp[i]=max(dp[i],dp[j]);
	dp[i]+=a[i];
}

定义dp[i]表示跳到第i格能得到的最大冰冻指数
i只能从i-r~i-l这些格子来

$dp[i]=max(dp[i],dp[j]+a[i])$

注意
2~l的格子是怎么也到不了的不要循环
i-r可能为负数，记得跟0取max

做完！
哦不，n有200000
只能接受O(nlogn)或者更强的O(n)算法
n什么logn，O(n)走起

我们看到在我们的朴素dp中我们的决策点占据了一个循环
就是说我们在把dp[j]转移成dp[i]时用了一层O(n)的循环
真是讨厌，把他优化掉
我们注意到
dp[i]=max(dp[i],dp[j])
只要求dp[j]的最大值就行了
单调队列能帮我们搞定这个问题
核心代码

int cnt=0;
dp[0]=0;
for(int i=l;i<=n;i++){
	while((!q.empty())&&q.back().data<=dp[cnt])
		q.pop_back();
	que u;
	u.id=cnt;u.data=dp[cnt];
	q.push_back(u);
	while(q.front().id<i-r)
		q.pop_front();
	dp[i]=q.front().data+a[i];
	cnt++;
}

cnt的存在是为了与我们的阶段i保持l的距离
这个操作很nice
完整代码就不放了

例题2 选择数字

dp的话是酱紫的
dp[i]表示1~i中我们选a[i]能得到的最大数字和
状态转移方程

$dp[i]=max(dp[i],dp[j-1]+sum[i]-sum[j])$

j是我们枚举的一个不选的点
i到j+1我们都要
这样每次只空1个是没问题的，毕竟我们要最大值啊
这里的时间复杂度为O(n^2)
这不可以！
我们将状态转移方程换一个形式
变成只跟j有关的max

$dp[i]=max(dp[i],dp[j-1]-sum[j])+sum[i]$

我们的单调队列维护dp[j-1]-sum[j]的最大值就好了
代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct que{
	int id;
	long long data;
};
long long ans=0;
long long sum[maxn];
long long dp[maxn];
deque<que>q;
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		sum[i]=sum[i-1]+x;
	}
	que tmp;
	tmp.id=0;tmp.data=0;
	q.push_back(tmp);
	//因为j是从1~i这里就不要像琪露诺那样用cnt了
	for(int i=1;i<=n;i++){
		while((!q.empty())&&q.back().data<=dp[i-1]-sum[i])
			q.pop_back();
		que u;
		u.id=i;u.data=dp[i-1]-sum[i];
		q.push_back(u);
		while(q.front().id<i-k)
			q.pop_front();
		dp[i]=q.front().data+sum[i];
	}
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	printf("%lld",ans);
    return 0;
}

练习1 [POI2015]WIL-Wilcze doły

至于题目名字，我也很无奈啊
主要是左端点不下降的这个结论很关键
可见这位巨佬的题解
我也不知道为什么我的代码和巨佬那么像..
代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000005;
struct que{
	int id;
	long long data;
};
int l[maxn];
long long c[maxn];
deque<que>q;
int main()
{
	int n,d,ans=0;
	long long p;
	scanf("%d%lld%d",&n,&p,&d);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		c[i]=c[i-1]+x;
	}
	l[d]=1;
	for(int i=d+1;i<=n;i++){
		while((!q.empty())&&q.back().data<=c[i]-c[i-d])
			q.pop_back();
		que u;
		u.id=i;u.data=c[i]-c[i-d];
		q.push_back(u);
		l[i]=l[i-1];//这里没必要用一个数组存
		while(q.front().id-d+1<l[i])
			q.pop_front();
		while((!q.empty())&&c[i]-c[l[i]-1]-q.front().data>p){
			l[i]++;
			while((!q.empty())&&q.front().id-d+1<l[i])
				q.pop_front();
		}
		ans=max(ans,i-l[i]+1);
	}
	printf("%d",ans);
	return 0;
}

练习2 跳房子

long long 是个巨坑
感觉这道题还挺模板的
二分+单调队列优化dp
代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
const long long inf=1e18;
struct que{
	int id,x;
	long long data;
}; 
struct node{
	int x,s;
}a[maxn];
int n,d,k;
long long dp[maxn];
deque<que>q;
bool check(int g){
	for(int i=1;i<=n;i++)dp[i]=-inf;
	q.clear();
	int cnt=0;
	dp[0]=0;
	for(int i=1;i<=n;i++){
		while(cnt<i&&a[i].x-a[cnt].x>=max(d-g,1)){
			while((!q.empty())&&q.back().data<=dp[cnt])
				q.pop_back();
			que u;
			u.x=a[cnt].x;u.data=dp[cnt];
			q.push_back(u);
			cnt++;
		}
		while((!q.empty())&&a[i].x-q.front().x>d+g)
			q.pop_front();
		if((!q.empty()))
			dp[i]=q.front().data+a[i].s;
		if(dp[i]>=k)
			return 1;
	}
	return 0;
}
void search(){
	int l=-1,r=a[n].x+1;
	while(l+1<r){
		int mid=l+((r-l)>>1);
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	if(r==a[n].x+1)
		printf("-1");
	else
		printf("%d",r);
}
int main()
{
	scanf("%d%d%d",&n,&d,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].s);
	search();
	return 0;
}

练习3 我要长高

oj好像死掉了

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005,inf=0x3f3f3f3f;
int ans=0;
int a[maxn];
int f[maxn][105];
deque<int>q1,q2;
int main()
{
	int n,c;
	while(scanf("%d%d",&n,&c)!=EOF){
		int maxa=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			maxa=max(maxa,a[i]);
			if(i>1)
				ans+=abs(a[i]-a[i-1]);
		}
		ans*=c;
		for(int i=1;i<a[1];i++)
			f[1][i]=inf;
		for(int i=a[1];i<=maxa;i++)
			f[1][i]=(i-a[1])*(i-a[1]);
		for(int i=2;i<=n;i++){
			q1.clear();
			q2.clear();
			for(int j=0;j<=maxa;j++){
				while((!q1.empty())&&f[i-1][q1.back()]-q1.back()*c>=f[i-1][j]-j*c)
					q1.pop_back();
				q1.push_back(j);
				if(j>=a[i])
					f[i][j]=f[i-1][q1.front()]-q1.front()*c+j*c+(j-a[i])*(j-a[i]);
				else
					f[i][j]=inf;
			}
			for(int j=maxa;j>=0;j--){
				while((!q2.empty())&&f[i-1][q1.back()]+q1.back()*c>=f[i-1][j]+j*c)
					q2.pop_back();
				q2.push_back(j);
				if(j>=a[i])
					f[i][j]=min(f[i][j],f[i-1][q2.front()]+q2.front()*c-j*c+(j-a[i])*(j-a[i]));
			}
		}
		for(int i=a[n];i<=maxa;i++)
			ans=min(ans,f[n][i]);
		printf("%d\n",ans);
	}
	return 0;
}