单调队列DP

最大子序和

题意

输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。

思考

状态表示-集合 $f_{i}$ : 以 $i$ 为 右端点, 长度 不超过 $m$ 连续子区间
状态表示-属性 $f_{i}$ : 区间的总和最大 $M a x$
状态计算 $f_{i}$ :

$$f_{i}=\max \left\{s_{i}-s_{j}\right\} \quad(1 \leq i-j \leq m)$$

观察这个转移方程, 首先这里的 $j$ 是有范围的: $i-m \leq j \leq i-1$
其次, $s_{i}$ 作为一个常量, 可以提到外面去: $f_{i}=s_{i}-\min \left\{s_{j}\right\} \quad(1 \leq i-j \leq m)$
从前向后 维护一个长度不超过 $m$ 的区间的 最小值, 就想到我们最熟悉的 滑动窗口模型 了

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100000,M=30010,INF = 0x3f3f3f3f,mod=998244353;
deque<int> qu;
int n,m;
LL s[300010],res;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    res=-1000000000000;
    qu.push_back(0);

    for(int i=1;i<=n;i++){
        if(!qu.empty()&& i - qu.front()>m){
            qu.pop_front();
        }
        res=max(res,s[i]-s[qu.front()]);
        while(!qu.empty()&&s[qu.back()]>=s[i]){
            qu.pop_back();
        }
        qu.push_back(i);
    }

    cout<<res<<endl;
    return 0;
}

修剪草坪

题意

给定一个长度为 n 的数组 w，其中 Wi 是第 i 个元素的 贡献

我们可以选择的 数组 中的一些元素，这些元素的贡献总和表示我们该种 方案 的 价值

但是，如果方案中出现选择了连续相邻且超过m个元素，则这些连续相邻的元素贡献归零

求解一种方案，使得选择的元素贡献总和 最大

思考

由于 连续选择 超过 $m$ 个元素时, 这些元素的 贡献 为 0 (相当于没选)
而本题, 所有的元素值都是 正整数, 故我们的方案中, 连续选择的元素数量 一定是不超过 $m$ 的

• 可以用 反证法 证明, 如果方案中有超过 $m$ 个连续元素, 则我们不选中间的一个, 使他断开, 必然不会使方案变差 于是, 我们就可以通过 最后一次没有选择的元素, 对 集合进行划分
  间氏DP分析法
  状态表示-集合 $f_{i}$ : 以 $i$ 为右端点的 前缀数组 的选择方案
  状态表示-属性 $f_{i}$ : 方案的 价值 最大 $M a x$
  状态计算： $$f_{i}=\max \left\{f_{j-1}+s_{i}-s_{j}\right\} \quad 0 \leq i-j \leq m$$ 跟上一题一样, 首先我们把 常量 提出来: $f_{i}=s_{i}+\max \left\{f_{j-1}-s_{j}\right\} \quad 0 \leq i-j \leq m$ 由于 $j$ 是有范围的: $i-m \leq j \leq i$, 于是问题就转化为 滑动窗口求极值 的问题了
  我们用一个记录 $f_{j-1}-s_{j}$ 的 单调递减 的队列 在 队头 维护一个 最大值 即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N], f[N];
int que[N];

LL g(int i)
{
    return f[max(0, i - 1)] - s[i];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]), s[i] += s[i - 1];

    int hh = 0, tt = 0; que[0] = 0;   //  0 <= i - j <= m
    for (int i = 1; i <= n; i ++ )
    {
        while (hh <= tt && g(i) >= g(que[tt])) tt -- ;
        que[ ++ tt] = i;  // i - j >= 0 故先入队
        while (hh <= tt && i - que[hh] > m) hh ++ ;
        f[i] = s[i] + g(que[hh]);
    }
    printf("%lld\n", f[n]);
    return 0;
}

旅行问题

题意

给定一个 环，环 上有 n 个节点，编号从 1∼n，以及一辆小车车。每一个 节点 i 有一个 权值 pi 表示当车到达该点时，可以获得的油量还有一个权值 di表示当车从 节点 i 到 节点 i+1 所需要 消耗的油量。现有一辆车想从环上任意点出发，顺时针或逆时针绕环一圈走回起点行驶的过程中，油量不能为负数，初始油量为起点处所能获得的油量判断能否完成环圈行驶。

3≤n≤10^6

思考

先破环成链。该区间合法必然等价于任意前缀获油量大于前缀使用量。

相对应的 前缀和 含义：

sd[i] ：从 1 出发到 i+1 所消耗的总油量
sp[i] ：从 1 出发到 i 所获得的总油量

状态表示-集合 $f_{i}$ : 以 $i$ 为 起点 和 终点, 顺时针 走一圈的方案
状态表示-属性 $f_{i}$ : 方案 是否可行 true
状态计算：

$$f_{i}=\left[\min \left\{\left(s p_{j}-s p_{i-1}\right)-\left(s d_{j}-s d_{i-1}\right)\right\} \geq 0\right] \quad(i \leq j \leq i+n-1)$$

和往常一样, 提出 常量 $: f_{i}=\left[s d_{i-1}-s p_{i-1}+\min \left\{s p_{j}-s d_{j}\right\} \geq 0\right] \quad(i \leq j \leq i+n-1)$ 这样就变成一个 滑动窗口求最小值 的问题了, 直接套 单调队列 即可
再推导一下滑动窗口的范围: $1 \leq i+n-j \leq n$

逆时针的走法:

状态表示-集合 $f_{i}$ : 以 $i$ 为 起点 和 终点, 逆时针 走一圈的 方案
状态表示-属性 $f_{i}$ : 方案 是否可行 true
状态计算：

$$\begin{gathered} f_{i}=\left[\min \left\{\left(s p_{i+n}-s p_{j-1}\right)-\left(s d_{i+n-1}-s d_{j-2}\right)\right\} \geq 0\right] \quad(i+1 \leq j \leq i+n) \\ f_{i}=\left[s p_{i+n}-s d_{i+n-1}+\min \left\{-s p_{j-1}+s d_{j-2}\right\} \geq 0\right] \quad(1 \leq j-i \leq n) \end{gathered}$$

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

typedef long long LL;

const int N = 1e6 + 10;
int n;
LL d[N],p[N],sd[N],sp[N];
bool f1[N];
deque<int> qu;
LL g(int j)
{
    return sp[j] - sd[j];
}
LL h(int j)
{
    return sd[j - 2] - sp[j - 1];
}
LL get1(int i, int j)
{
    return sd[i - 1] - sp[i - 1] + g(j);
}
LL get2(int i, int j)
{
    return sp[i + n] - sd[i + n - 1] + h(j);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i],&d[i]);
        p[i+n]=p[i];
        d[i+n]=d[i];
    }
    for (int i = 1; i <= n << 1; i ++ ){
        sd[i] = sd[i - 1] + d[i];
        sp[i] = sp[i - 1] + p[i];
    }

    for(int i=1;i<=n<<1;i++){
        if(qu.size()&&i-qu.front()>n) qu.pop_front();
        if(i>n){
            if(get1(i-n,qu.front())>=0)
                f1[i-n]=true;
        }
        while(qu.size()&&g(qu.back())>=g(i)) qu.pop_back();
        qu.push_back(i);
    }

    qu.clear();
    for (int i = n << 1; i; i -- )
    {
        while (qu.size()&&qu.front()-i>n) qu.pop_front() ;
        if (i <= n){
            if (get2(i, qu.front()) >= 0){
                f1[i] = true;
            }
        }
        while (qu.size()&&h(qu.back())>=h(i)) qu.pop_back() ;
        qu.push_back(i);
    }
    for (int i = 1; i <= n; i ++ )
        puts(f1[i] ? "TAK" : "NIE");
    return 0;
}

理想的正方形(二维滑动窗口)

题意

有一个 a×b的整数组成的矩阵，现请你从中找出一个 n×n 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

思考

我们可以预处理出每列的行中最值，再对该列求一个最值，就是该子矩阵的最值

该降维手段，使得一个 二维滑动窗口问题 变成了 n行+n列 的 一维滑动窗口问题

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

typedef long long LL;

const int N=1e5+10;
int m,n,k;
int min_row[1010][1010];
int max_row[1010][1010];
int mp[1010][1010];
int ax[1010],bx[1010],cx[1010];

void getmax(int aa[],int bb[],int len){
    deque<int> qu;
    for(int i=1;i<=len;i++){
        if(qu.size()&&qu.front()<=i-k) qu.pop_front();
        while (qu.size()&&aa[qu.back()]<=aa[i]){
            qu.pop_back();
        }
        qu.push_back(i);
        bb[i]=aa[qu.front()];
    }
}
void getmin(int aa[],int bb[],int len){
    deque<int> qu;
    for(int i=1;i<=len;i++){
        if(qu.size()&&qu.front()<=i-k) qu.pop_front();
        while (qu.size()&&aa[qu.back()]>=aa[i]) qu.pop_back();
        qu.push_back(i);
        bb[i]=aa[qu.front()];
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        getmax(mp[i],max_row[i],m);
        getmin(mp[i],min_row[i],m);
    }
    int res=0x3f3f3f3f;
    for(int i=k;i<=m;i++){
        for(int j=1;j<=n;j++) ax[j]=min_row[j][i];
        getmin(ax, bx, n);

        for(int j=1;j<=n;j++) ax[j]=max_row[j][i];
        getmax(ax, cx, n);

        for(int j=k; j<=n;j++) res=min(res,cx[j]-bx[j]);
    }
    cout<<res;
    return 0;
}