单调队列优化DP

单调队列优化dp

单调队列可以求某固定区间的最值，所以dp中需要求某固定区间的最值则可以考虑使用单调队列优化

单调队列-滑动窗口

https://www.luogu.com.cn/problem/P1886

/*
 * @Author     : Danc1ng
 * @Date       : 2024-04-24 16:06:34
 * @FilePath   : P1886 滑动窗口 [模板]单调队列
 * @Origin     : https://www.luogu.com.cn/problem/P1886
 * @Description:
 * @Solution   :
 */



#include <bits/stdc++.h>
#define bug cout << "***************" << endl
#define look(x) cout << #x << " -> " << x << endl
#define endl '\n'
#define int long long
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;

using namespace std;
typedef pair<int, int> PII;

constexpr int N = 1e6 + 10 , INF = 2e9;

int n,k;
int a[N];

void sliding_window_minimum_deque()
{
    deque<int> q;
    //队列保存数组下标
    //滑动窗口最小值
    for(int i=0;i<n;i++)
    {
        //到当前位置时队列长度>k 弹出队头
        if(q.size()&&i-k+1>q.front()) q.pop_front();

        //保存最小值 所以队列最后的数比新加进来的数还要大 说明之后的答案也不会是他 直接弹出
        while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
        //加入当前数
        q.push_back(i);

        //符合长度为k的窗口下标时 打印答案
        if(i>=k-1) cout<<a[q.front()]<<' ';
    }
    cout<<endl;
}

void sliding_window_maximum_deque()
{
    deque<int> q;
    for(int i=0;i<n;i++)
    {
        if(q.size()&&i-k+1>q.front()) q.pop_front();

        while(q.size()&&a[q.back()]<=a[i]) q.pop_back();

        q.push_back(i);

        if(i>=k-1) cout<<a[q.front()]<<' ';
    }
    cout<<endl;
}

void sliding_window_maximum_normal()
{
    vector<int> q(n);
    //数组模拟单调队列
    int hh=0,tt=-1;

    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>q[hh]) hh++;

        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;

        if(i>=k-1) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;

}


void solve()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];

    sliding_window_minimum_deque();

    sliding_window_maximum_normal();

}


signed main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","r",stdin);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    solve();

    return 0;
}

P2034选择数字

https://www.luogu.com.cn/problem/P2034

solution:

f[i][1/0]表示考虑前i个数且第i个数选或不选

f[i][0]=max(f[i-1][0],f[i-1][1]) 第i个不选则看前i-1个选或不选的最大值

考虑f[i][1] 如果第i个数要选 因为最多选连续k个所以第i个数前面能选的数最多连续k-1个
注意到a[i]是非负整数 所以能选就选 则如果i前面的j不被选 则后面j+1到i-1的位置都可以选

i-k,i-k+1,i-k+2,.... i-2,i-1,i
⬆ .... ..... ..... ⬆

f[i][1]=max(f[j][0]+a[i]+a[i-1]+...a[j+1]) 后面a[i]+a[i-1]+....a[j+1]可用前缀和快速求出 所以
f[i][1]=max(f[j][0]+s[i]-s[j])=max(f[j][0]-s[j])+s[i]; (i-k<=j<=i-1)

如果暴力求出max(f[j][0]-s[j])则时间复杂度是O(n^2) 观察到每次j的范围长度都是(i-1)-(i-k)+1=k 是固定的
求固定长度的最值可以用滑动窗口 所以O(1) 即可求出max(f[j][0]-s[j])

/*
origin:https://www.luogu.com.cn/problem/P2034

description：给定一行 n 个非负整数 现在你可以选择其中若干个数，但不能有超过 

标签：DP,队列,max,个数,back,int,单调,https,dp	

From： https://www.cnblogs.com/Danc1ng/p/18158962