单调队列优化DP

2024-02-02 18:20:46

单调队列优化DP

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

先以最大子序和这道题理解单调队列优化DP的思想。

[AcWing135.最大子序和](135. 最大子序和 - AcWing题库)

求连续子序列的和，必然采用前缀和的思想。
所有连续子序列的最大值，肯定是至少以某一结点i为头/尾扫一遍整个序列。
但是对于某一个序列尾结点i，我们之前枚举尾结点的时候已经扫过i前面的数了，再扫一遍岂不是很丑陋的O(n^2)。
单调队列就是用来优化这种问题的方法。

对于从左到右扫描的 k < j < i ，如果S[j] <= S[k]，对于右节点 i ，完全没必要再考虑k了。一是因为同样的 S[i] 减去更小的左端点前缀和 S[j] 得到的序列和肯定更大；二是因为 j 更靠右边，存活的时间更长。

因此，在我们从左到右扫描的过程中，采用一个队列来保存扫描过的结点 i ，要求S[i] 单调递增。

而在寻找最大连续子区间的时候，只需要找到队列首位（且满足序列长度小于等于M）的那个，就一定是左端点的最优解。由于每个元素只入队/出队一次，所以时间复杂度是O(N)。

单调队列的优化思想是：在O(n)的时间复杂度下，减少另一端点的枚举范围，使时间复杂度从O(n^2)降低到O(n)，妙就妙在维护队列的单调性不需要太多多余操作，只需将队列元素和当前元素对比并判断是否出队即可。

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N = 3e5+10;

int a[N];
int sum[N];
int q[N];

int main()
{
    scanf("%d %d",&n,&m);
    
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    
    int hh = 0,tt = 0;
    int res = -0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        while(hh<=tt && (i-q[hh])>m) hh++;  //注意前缀和的性质！，sum[i] - sum[q[hh]]表示的是区间，[q[hh]+1,i]，所以这里的闭区间算长度不加1！
        res = max(res, sum[i] - sum[q[hh]]);
        while(hh<=tt && sum[q[tt]] >= sum[i]) tt--;
        q[++tt] = i;
    }
    
    cout<<res<<endl;
    
    return 0;
}

[AcWing1087.修剪草坪](1087. 修剪草坪 - AcWing题库)

Tag：线性DP + 单调队列优化

状态： f[i] 代表前 i 个中选取不超过连续 m 个的最大值。属性：MAX

状态转换：对于最后一个元素 i，有选和不选两种方式。

不选择第 i 个元素，则情况转化为 f[i-1] 。（无需考虑连续的问题）
选择第 i 个元素，则情况转化为，对于选择的最后连续的一段，选几个最好？

设选择了 j 个，其中(1 <= j <= m)，因为至少要选 i 号元素，至多不能超过m个。

转移方程为：

f [ i ] = max{ s[ i ] - s[ i - j ] + f [ i - j - 1 ] } ( 1 <= j <= k)

= max{ f [ i - j - 1 ] - s [ i - j ] } + s [ i ]

如果将max函数内部的运算看作 g( i - j ) 的话，相当于建立一个单调队列，维护 g(i - j )的递减序列，由于 j 的限制是 (1 <= j <= k)，则维护 i 之前最多 k 个即可。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
typedef long long LL;
LL a[N];
LL s[N];
LL f[N];
int q[N];
int n,m;

LL g(int i)
{
    return f[i-1] - s[i];
}

int main()
{
    scanf("%d %d",&n,&m);
    
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        s[i] = s[i-1] + a[i];
    }
    
    int hh=0, tt=0;
    LL res = 0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh] < i-m) hh++;
        f[i] = max(f[i-1],s[i] + g(q[hh]));     //注意利用闫氏DP分析法时，分成了选i和不选i两种，而单调队列是对选i进行了优化，还有和不选i
        //即f[i-1]进行比较
        while(hh<=tt && g(q[tt]) <= g(i)) tt--; //维护递减子序列
        q[++tt] = i;
    }
    
    cout<<f[n]<<endl;
    
    return 0;
}

[AcWing1088.旅行问题](1088. 旅行问题 - AcWing题库)

Tag：单调队列DP + 环形问题

单调队列一般用来处理区间最小值问题

本题几个特殊的点：

把 p[ i ] 和 d[ i ] 综合处理，即每个点保存 p[i] - d[i] ，sum[i] 也保存这个点的 p[ i ] - d[ i ] 的前缀和。
破环为链。环形问题的基本操作。
顺时针和逆时针的顺序问题。考察的是每个点的可行性，肯定是顺时针走一圈逆时针走一圈，两种里面有任意一种能走都会设置为1。

和前面两个题目的不同点是：
- 这个题是确定起点，去找终点；而不是像之前的两题，已经有了一个终点，问从哪一个起点走来最好。
- 所以自第一遍顺时针的时候需要逆向处理，滑动窗口中保存的是，距离不超过n的，逆序的递增序列。所以，滑动窗口的队首才是 [i, i+n] 之间前缀和的最小值。如果最小值可行，那整个序列都可行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

typedef long long LL;

const int N=2e6+10;

int n;
int o[N],dist[N];
LL s[N];
int q[N];
bool ans[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&o[i],&dist[i]);
        s[i]=s[i+n]=o[i]-dist[i];
    }
    
    //破环成链  处理出前缀和
    for(int i=1;i<=n*2 ;i++) s[i]+=s[i-1];
    
    //逆向处理
    int hh=0,tt=0;
    q[0]=n*2+1;
    for(int i=n*2;i>=0;i--)
    {
        if(q[hh]>i+n) hh++;
        if(i<n) //逆向的时候在i<n的时候转一圈
        {//事实上，这里应该判断s[q[hh]]-s[i]>=0 更好理解
            if(s[i]<=s[q[hh]]) ans[i+1]=true;
        }//维持单调性
        while(hh<=tt && s[q[tt]]>=s[i]) tt--;
        q[++tt]=i;
    }
    
    dist[0]=dist[n];
    for(int i=1;i<=n;i++) s[i]=s[i+n]=o[i]-dist[i-1];
    for(int i=1;i<=n*2;i++) s[i]+=s[i-1];
    
    //正向处理
    hh=0,tt=0;
    q[0]=0;
    for(int i=1;i<=n*2;i++)
    {
        if(q[hh]<i-n) hh++;
        if(i>n) 
        {
            if(s[i]>=s[q[hh]]) ans[i-n]=true;
        }
        while(hh<=tt && s[q[tt]]<=s[i]) tt--;
        q[++tt]=i;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(ans[i]) puts("TAK");
        else puts("NIE");
    }   
    return 0;
}

要铭记前缀和的性质，if(s[i] <= s[q[hh]]) ans[i+1] = true;，其中s[ i ]只能确定 ans[i+1]是否成立，就是因为区间 [i+1 ~ i+n] 是由 s[i + n] 和 **s[ i ] **确定的。

[AcWing1089.烽火传递](1089. 烽火传递 - AcWing题库)

和前面几个题目不同，前面几个题目利用的前缀和处理区间和问题，本题直接利用单调队列的性质，裸单调队列DP。

确定好状态划分之后，手撕还是很容易的。

#include<bits/stdc++.h>
using namespace std;


int n,m;
const int N = 2e5+10;
int a[N];
int q[N];
int f[N];
//f[i] 表示 以 i 结尾的选择方案中的最小值。 

int main()
{
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	int hh = 0, tt = 0;
	f[0] = 0;
	for(int i = 1;i<=n;i++)
	{
		while(hh<=tt && q[hh]<i-m) hh++;
        //每一次优化当前的结果，直接加队首的最小值就一定是最优解。
		f[i] = f[q[hh]] + a[i];
		while(hh<=tt && f[q[tt]]>=f[i]) tt--;
        //维护的是 递增序列， 队首为最小值。
		q[++tt] = i;
	}
	
	int res = 0x3f3f3f3f;
	for(int i=n-m+1;i<=n;i++)
	{
		res = min(res, f[i]);
	}
	
	printf("%d\n",res);
	
	return 0;
}

[AcWing.1090绿色通道](AcWing 1090. 绿色通道 - AcWing)

单调队列一定要确定滑动窗口的大小，所以，可以采用二分的方法来确定，滑动窗口（即空题段）的大小。

注意本题的要求是空题段。在处理边界问题时要尤其注意。当 q[hh] < i - limit - 1 才不符合题意，这个自己画个图就很容易理解了。

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4+10;

int n,t;
int w[N];
int f[N];
int q[N];

bool check(int limit)
{
	memset(f,0,sizeof f);
	
	int hh = 0, tt = 0;
	for(int i = 1;i<=n;i++)
	{
	    //注意limit的定义是 空题段
		while(hh<=tt && q[hh] < i - limit - 1) hh++;
		f[i] = f[q[hh]] + w[i];
		while(hh<=tt && f[q[tt]] > f[i]) tt--;
		//维护递增序列，队首是最小值
		q[++tt] = i; 
	}
	
	for(int i = n - limit;i<=n;i++)
	{
		if(f[i]<=t)
		return true;
	}
	return false;
}

int main()
{
	scanf("%d %d",&n,&t);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	
	int l = 0, r = n;
	while(l<r)
	{
		int mid = (l+r)>>1;
		if(check(mid)) r = mid;
		else l = mid +1;
	}
	cout<<l<<endl;
	
	return 0;
}

[AcWing1091.理想的正方形](1091. 理想的正方形 - AcWing题库)

区间最大/小值求法：

在行方向上设置n长的滑动窗口，然后每一次都在最右边保存它和它左边n-1个元素的最大值。
然后再对每一列，求出其中的最大值，即为当前 n*n 的方阵的最大值。
最小值同里。

利用单调队列优化，可以在处理最大值时，行方向 O(a*b)，列方向O(a * b)，求最小值统里，故总得时间复杂度就是O(a * b)。(在整个数据矩阵是 a * b 的情况下)。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1010, INF = 1e9;
int a[N];
int w[N][N];
int n,m,k;
int row_min[N][N],row_max[N][N];
int q[N];
//get_min()或get_max()函数，都是对数组a进行单调队列求最小(大)值，并将值放入数组b中保存。
void get_min(int a[],int b[],int tot)
{
	int hh = 0, tt = -1;
	for(int i=1;i<=tot;i++)
	{
		while(hh<=tt && q[hh]<=i-k) hh++;
		while(hh<=tt && a[q[tt]]>=a[i]) tt--;
		q[++tt] = i;
		b[i] = a[q[hh]];
	}
}

void get_max(int a[],int b[],int tot)
{
	int hh=0,tt=-1;
	for(int i=1;i<=tot;i++)
	{
		while(hh<=tt && q[hh]<=i-k) hh++;
		while(hh<=tt && a[q[tt]]<=a[i]) tt--;
		q[++tt] = i;
		b[i] = a[q[hh]];
	}
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        scanf("%d",&w[i][j]);
    }
    
    for(int i=1;i<=n;i++)
    {
        get_min(w[i],row_min[i],m);
        get_max(w[i],row_max[i],m);
    }
	
    int res=INF;
    int a[N],b[N],c[N];
    for(int i=k;i<=m;i++)
    {
        for(int j=1;j<=n;j++) a[j]=row_min[j][i];
        get_min(a,b,n);
        
        for(int j=1;j<=n;j++) a[j]=row_max[j][i];
        get_max(a,c,n);
        
        for(int j=k;j<=n;j++) res=min(res,c[j]-b[j]);
    }
    
    printf("%d\n",res);
    
    return 0;
}

总得来说，单调队列可以用来求范围内的最值维题。在遍历数据的过程中，它抱持了队列中的单调性，无论是队列是根据前缀和亦或是 dp值保存的，队首都能返回符合约束条件的最大 / 最小值。我认为，单调队列一般是把需要重复遍历的 O(n^2) 时间复杂度降低到 O(n) （每个元入队 / 出队一次）的时间复杂度。

码农公寓