单调队列优化DP

单调队列优化DP

单调栈和单调队列都是借助单调性，及时排除不可能的决策，保持候选集合的高度有效性和秩序性。单调队列尤其适合优化决策取值范围的上、下界均单调变化，每个决策在候选集合中插入或删除至多一侧的问题。

利用单调队列，我们可以舍去许多无用的状态，来更快的找出最优解。

一般用单调队列维护的都是根据题目而定，比如求 XX 最小值，那么我们就要维护一个单调递增的队列，因为这样队头的元素是始终最小的；反之求 XX 最大值，我们就要维护一个单调递减的队列，因为这样队头元素始终是最大的。

持续更新题目中，约为三天

最大子序和

显然最朴素的方法是直接暴力，但是 \(3\times 10^{5}\) 的数据范围是不会让我们 AC 的。

我们考虑利用单调队列来优化一下复杂度。

首先我们看到求连续的一段的和，所以我们先预处理出前缀和。

首先我们知道如果当前遍历到的元素的下标减去队列头的元素是大于 \(m\) 的话，这个是不合法的，所以我们每到了一个点都要先把这些不合法的都给弹出去，然后在进行求解。

我们维护一个单调递增的队列，这样我们的头部元素保证是这个区域内最优的一块，然后我们统计答案直接用当前点的前缀和减去头部第一个元素的下标对应的前缀和就好了。

code:

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define N 1000100
using namespace std;
int n,m,a[N],sum[N],q[N],h,t,ans=-INF;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
	{
		while(h<=t&&i-q[h]>m)h++;
		ans=max(ans,sum[i]-sum[q[h]]);
		while(h<=t&&sum[q[t]]>=sum[i])t--;
		q[++t]=i;
	}
	cout<<ans<<endl;
	return 0;
}

围栏

我们设 \(f[i][j]\) 表示前 \(i\) 个人粉刷前 \(j\) 块木板的最大花费。

我们对于每一个人，枚举每一块木板，我们都有以下三种情况：

1. 当前人不粉刷，f[i][j]=max(f[i-1][j],f[i-1][j])

2. 当前人粉刷，但是不粉刷当前木板 f[i][j]=max(f[i][j-1],f[i][j])

3. 当前人粉刷且粉刷当前木板、

第三种情况又分为两种情况。

1. 当前的 \(j<s_{i}\)，只能做左端点，因为必须包含 \(s_{i}\)，所以这个时候，我们维护一个以队列里的点为起点时花费最大的花费单调递增的队列，也就是说，我们队列里面是左端点，但是我们里面单调递增的，是未计算当前粉刷的区间时最大的花费。

2. 当前点 \(j>=s_{i}\)，只能做右端点，这个时候我们判断一下队列里的元素是否和当前点的最大长度不超过 \(l\)，然后我们进行计算，设我们从里面取出的左端点为 \(k\)，则 f[i][j]=max(f[i][j],f[i-1][k]+(j-k)*p_{i})。

然后就得出答案了。

code:

#include<bits/stdc++.h>
#define N 100010
#define M 110
using namespace std;
int n,m,q[N],f[M][N];
struct sb{int l,p,s;}e[N];
inline int cmp(sb a,sb b){return a.s<b.s;}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>e[i].l>>e[i].p>>e[i].s;
	sort(e+1,e+m+1,cmp);//按必须包含的木板s来从小到大排序 
	for(int i=1;i<=m;i++)//枚举每一个工匠 
	{
		int h=0,t=0;//头尾指针 
		for(int j=0;j<=n;j++)
		{
			f[i][j]=f[i-1][j];//当前工人不用 
			if(j)f[i][j]=max(f[i][j],f[i][j-1]);//当前木板不粉刷 
			int l=e[i].l,p=e[i].p,s=e[i].s;//区间最大长度，单位花费，必须包含的木板 
			if(h<=t&&q[h]<j-l)h++;//如果要是队列里最靠左的元素在当前的区间左边，我们直接弹出 
			if(j>=s&&h<=t)//如果要是当前点大于s且队列不空，那j就只能是区间右端点
			{
				int k=q[h];//取出队头元素
				f[i][j]=max(f[i][j],f[i-1][k]+p*(j-k));//取max
			}
			if(j<s)//如果要是当前点不包含s就只能做左端点 
			{
				while(h<=t&&f[i-1][q[t]]-q[t]*p<=f[i-1][j]-j*p)t--;//如果以当前的尾部元素为起点的话不如以当前点为起点更优就弹出，维护队列内的起点的价值单调递增 
				q[++t]=j;//入列 
			}
		}
	}
	cout<<f[m][n]<<endl;//输出m个工匠粉刷n个木板的最大收益 
	return 0;
}

P1725 琪露诺

我们观察题目，发现如果要是从一点点转移到一个区间是不好转移的，所以我们转化一下问题，变为当前点由那些点转移过来，这样我们就可以由已经处理好的问题来处理当前的问题了。

我们手模一下可以发现，点 \(i\) 只能由 \([i-R,i-L]\) 转移而来，所以我们直接用一个单调队列来维护里面的 \(f[k]\) 单调递减，也就是说，我们每次到了点 \(i\) 都把当前最大能转移到 \(i\) 的点给放入队列，然后维护一个单调递减的队列，这样让我们的头部元素始终是最优的，我们就可以通过头部元素转移到当前点；当然我们也要判断是否在这个区间内，把不合法的先弹出去。

code:

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define N 1000100
using namespace std;
int n,L,R,a[N],f[N],q[N],h,t=-1,ans=-INF;
signed main()
{
	cin>>n>>L>>R;
	for(int i=0;i<=n;i++)cin>>a[i];
	memset(f,-127,sizeof f);
	f[0]=0;
	for(int i=L;i<=n;i++)
	{
		while(h<=t&&f[q[t]]<=f[i-L])t--;
		q[++t]=i-L;
		while(h<=t&&q[h]<i-R)h++;
		f[i]=f[q[h]]+a[i];
//		for(int j=h;j<=t;j++)cout<<f[q[j]]<<" ";cout<<endl;
		if(i>n-R)ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	return 0;
}