单调队列优化DP

单调队列优化dp

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

单调队列-滑动窗口

/** @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选择数字

/*
origin:https://www.luogu.com.cn/problem/P2034description：给定一行 n 个非负整数 现在你可以选择其中若干个数，但不能有超过 𝑘个连续的数字被选择。
你的任务是使得选出的数字的和最大。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])*/#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 s[N];
int f[N][2];void solve()
{cin>>n>>k;for(int i=1;i<=n;i++){int x;cin>>x;s[i]=s[i-1]+x;}deque<int> q;for(int i=1;i<=n;i++){//更新当前的f[i][1/0];f[i][0]=max(f[i-1][0],f[i-1][1]);if(i<=k){f[i][1]=s[i];}else{int now=f[q.front()][0]-s[q.front()];f[i][1]=now+s[i];}//维护单调队列if(q.size()&&q.front()<i-k+1) q.pop_front();while(q.size()&&(f[i][0]-s[i]>=f[q.back()][0]-s[q.back()])) q.pop_back();q.push_back(i);}cout<<max(f[n][0],f[n][1])<<endl;}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;
}

Acwing 1089. 烽火传递

n个数连续k个里面只用选1个

/*
origin:https://www.acwing.com/problem/content/1091/
silution:
dp[i]表示前i个且选第i个的最小值
dp[i]=min(dp[j])+a[i];i-m,i-m+1,i-m+2,....i-2,i-1,i;
如果i选了 则至少i-m得选*/#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 = 2e5 + 10 , INF = 2e9;int n,m;
int a[N];
int dp[N];void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];deque<int> q;q.push_back(0);for(int i=1;i<=n;i++){//维护队头if(q.size()&&q.front()<i-m) q.pop_front();//更新dp[i]dp[i]=dp[q.front()]+a[i];//更新队列while(q.size()&&dp[q.back()]>=dp[i]) q.pop_back();q.push_back(i);}int res=INF;for(int i=n-m+1;i<=n;i++)res=min(res,dp[i]);cout<<res<<endl;}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;
}

LC2944

/** @Author     : Danc1ng* @Date       : 2024-04-24 20:31:43* @FilePath   : LC2944* @Origin     :https://leetcode.cn/problems/minimum-number-of-coins-for-fruits/description/* @Description:给一个长度为n的数组a,每个元素被选需要花费w[i],如果选中第i个元素则后面i个元素可以免费被选择* 如果第i个元素可以被免费选择也可以再次花费w[i]选择它,求选择所有元素的最小花费** @Solution   :dp[i]表示前i个水果都被选中且i是花钱买的的最小金币数* dp[i]=min(dp[j])+w[i]  i/2<=j<i***/class Solution {
public:int minimumCoins(vector<int>& prices) {int n=prices.size();//f[i]表示前i个数被选中且i花钱选的最小花费auto solve_N2=[](int n,vector<int> prices){vector<int> f(n+5,INT_MAX);f[0]=0;for(int i=1;i<=n;i++){//枚举上一次购买的水果 2*j>=ifor(int j=(i+1)/2;j<=i;j++)f[i]=min(f[i],f[j-1]+prices[j-1]);}return f[n];};//单调队列维护f[j-1]+prices[j-1]的最小值auto solve_N=[](int n,vector<int> prices){vector<int> f(n+5,INT_MAX);f[0]=0;deque<int> q;for(int i=1;i<=n;i++){if(q.size()&&2*q.front()<i) q.pop_front();while(q.size()&&f[q.back()-1]+prices[q.back()-1]>=f[i-1]+prices[i-1]) q.pop_back();q.push_back(i);f[i]=f[q.front()-1]+prices[q.front()-1];}return f[n];};return solve_N(n,prices);}
};

Acwing 4418. 选元素

/** @Author     : Danc1ng* @Date       : 2024-04-24 20:21:51* @FilePath   : Acwing 4418. 选元素* @Origin     :https://www.acwing.com/problem/content/description/4421/* @Description:请你从中挑选 x个元素，要求：1.原序列中的每一个长度为k的连续子序列都至少包含一个被选中的元素。满足条件1的前提下，所选 x个元素的相加之和应尽可能大。输出最大可能和。* @Solution   ：f[i][j]表示在前i个数中选j个数且第i个数被选上的最大和
因为第j个数在第i个位置被选中 而长度为k的连续子序列都至少包含一个被选中的元素
所以第j-1个数应该在[i-k,i-1]的位置被选择f[i][j]=max(f[i][j],f[t][j-1]+w[i]) i-k<=t<i*/#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 = 2e2 + 10 , INF = 2e9;int n,k,x;
int f[N][N];
int w[N];void solve()
{cin>>n>>k>>x;for(int i=1;i<=n;i++) cin>>w[i];memset(f,-0x3f,sizeof f);f[0][0]=0;//选的个数for(int i=1;i<=x;i++){//选的位置deque<int> q;q.push_back(0);for(int j=1;j<=n;j++){if(q.size()&&q.front()<j-k) q.pop_front();if(q.size()) f[j][i]=f[q.front()][i-1]+w[j];while(q.size()&&f[q.back()][i-1]<=f[j][i-1]) q.pop_back();q.push_back(j);}}int res=-1;for(int i=n-k+1;i<=n;i++){res=max(res,f[i][x]);}cout<<res<<endl;}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;
}