1、 烽火传递
朴素的dp过程不难理解,dp[i]表示：考虑前i个烽火台 且第i个点燃状态下的最小代价。 dp[i]=min(dp[j])+a[i] ( i-m<=j<=i-1)
j的范围：在考虑i之前，i前面的m个元素，必须取1个，比如i=7，m=3 ，考虑i=7之前，4 5 6中必须取1个。
用单调队列可以优化这种类问题。
所谓单调队列 ，就是 不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。 保证每次查询区间最值时可以用O（1）时间查到。
维护单调队列时，对于新元素，我们先按照单调性从队尾删去部分元素，再让新元素入队，保证单调性不变 。然后由于更新队首，把超出区间长度的元素丢出去。
注：单调队列存的是数组下标，不是真的存值。而且队头到队尾的元素，也就是下标是递增的，表示入队的时间先后。
//#pragma comment(linker, "/STACK:102400000,102400000")//手动扩栈 #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<deque> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=0x3f3f3f3f; const double eps=1e-5; const int maxn=2e5+7; deque<int> dq;//单调队列 递增 LL dp[maxn];//前i个烽火台 且第i个点燃的最小代价 int n,m,v[maxn]; int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",v+i); } dq.push_front(0);//这题我们初始化队列为0，可以保证前m个当中不会取超过2个元素 for(int i=1;i<=n;i++) { dp[i]=v[i]; if(dq.size()) dp[i]+=dp[dq.front()]; //入队 while(dq.size() && dp[dq.back()]>dp[i]) dq.pop_back(); dq.push_back(i); //队首出队 while(dq.size() && dq.front()<i-m+1) dq.pop_front(); } LL ans=dp[n]; for(int i=n-1;i>n-m;i--) ans=min(ans,dp[i]); cout<<ans; //system("pause"); return 0; }2、最大连续和 LibreOJ - 10176
题意：给定序列，求其中长度不超过m的最大子段和 (n,m<=2e5)
思路：先把子段和转化成前缀和相减：sum[i]-sum[j] ,sum表示前缀和
于是问题等价为，求sum数组中满足i-j<m的最大的（sum[i]-sum[j]）
我们普通做法是 对于每一个i ，在[i-m+1,i-1]中枚举找到最小的sum[j]，这样才能使得对于当前的i，sum[i]-sum[j]最大，但是这样肯定超时
用一个单调队列维护sum数组中所处区间的长度不超过m的的递增子序列 ,对于每一个i更新维护。
#include<bits/stdc++.h> using namespace std; #define Please return #define AC 0; #define LL long long const int maxn=2e5+7; int n,m; int sum[maxn]; deque<int> deq; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); sum[i]=sum[i-1]+t; } int ans=sum[1]; deq.push_back(0);//放入一个0元素，保证前m个元素的前缀和可以全部取到 for(int i=1;i<=n;i++) { ans=max(ans,sum[i]-sum[deq.front()]); while(deq.size() && sum[deq.back()]>sum[i]) deq.pop_back(); deq.push_back(i); while(deq.size() && deq.front()<i+1-m) deq.pop_front(); } cout<<ans<<'\n'; Please AC }3.修剪草坪 LibreOJ - 10177 （烽火传递改编）
思路：先把这些数全取了，再去掉某些数使得原序列任意k+1个数就有一个数属于被去掉的范畴，这就和第一题烽火传递是一样的思路了 。求出去掉这些数的最小和即可。
#include<bits/stdc++.h> using namespace std; #define Please return #define AC 0; #define LL long long const int maxn=2e5+7; //dp[i]表示只考虑前i个数 第i个数去掉的最优解 //dp[i]=min(dp[j])+a[i] i-(k+1)<=j<i //用单调队列维护一个递增序列 int n,k; LL dp[maxn],a[maxn]; LL ans=0; deque<int> deq; int main() { scanf("%d %d",&n,&k); k++;//每k+1个数中要有一个被去掉 for(int i=1;i<=n;i++) { scanf("%lld",a+i); ans+=a[i]; } deq.push_back(0); for(int i=1;i<=n;i++) { dp[i]=a[i]; if(deq.size()) dp[i]+=dp[deq.front()]; while(deq.size() && dp[deq.back()]>dp[i]) deq.pop_back(); deq.push_back(i); while(deq.size() && deq.front()<i+1-k) deq.pop_front(); } LL mmin=dp[n]; for(int i=n-1;i>n-k;i--) mmin=min(mmin,dp[i]); cout<<ans-mmin<<'\n'; Please AC }3、绿色通道 LibreOJ - 10181
思路：二分每mid个数就要去掉1个，然后用dp验证可行性，验证过程的代码和烽火传递是一样的。 最终答案就是mid-1。
#include<bits/stdc++.h> using namespace std; #define Please return #define AC 0; #define LL long long const int maxn=2e5+7; //题意：给定长度为n的序列，每个数就是一个代价，最多花费t代价，取某些数，要求不取的子段长度最小，求最小长度 //思路：二分，用dp去判断可行性 int n,t; int a[maxn]; int dp[maxn];//前i题 i取 最小代价 小于等于t则可行 deque<int> deq; //dp[i]=min(dp[j])+a[i] (i-N<=j<i) bool check(int N)//和烽火传递的代码一样 ，每N个数就必须有一个取 { memset(dp,0,sizeof(dp)); deq.clear();//维护一个递增序列 deq.push_back(0); for(int i=1;i<=n;i++) { dp[i]=a[i]; if(deq.size()) dp[i]+=dp[deq.front()]; while(deq.size() && dp[deq.back()]>dp[i]) deq.pop_back(); deq.push_back(i); while(deq.size() && deq.front()<i+1-N) deq.pop_front(); } int ans=dp[n]; for(int i=n-1;i>n-N;i--) ans=min(ans,dp[i]); return t>=ans; } void solve() { int ans; int l=0,r=n; while(l<=r) { int mid=(l+r)/2;//mid表示 原序列中每mid个数就要去掉一个 ，最终答案就是mid-1 if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans-1; } int main() { scanf("%d%d",&n,&t); bool ok=0; for(int i=1;i<=n;i++) { scanf("%d",a+i); if(a[i]<=t) ok=1; } if(!ok) printf("%d\n",n); else solve(); Please AC }4.理想的正方形 LibreOJ - 10182
思路：这题和最大子矩阵的预处理是一样的，把1列压缩成1格，用max_g[][],min_g[][]表示 用两个单调队列分别维护最大值和最小值
预处理完max_g,min_g后，枚举前面a-n+1行，对于每行，相当于一个一维的数列要你求n长度区间的最大最小差值 。经典单调队列题
#include<bits/stdc++.h> using namespace std; #define Please return #define AC 0; #define LL long long const LL INF=2e18+7; const int maxn=1e3+7; int g[maxn][maxn]; int max_g[maxn][maxn],min_g[maxn][maxn];//第i行 第j列格子，往下n-1格中的最大最小值 deque<int> deq1,deq2;//递减和递增 int a,b,n; int ans=2e9+7; int main() { scanf("%d%d%d",&a,&b,&n); for(int i=1;i<=a;i++) { for(int j=1;j<=b;j++) scanf("%d",&g[i][j]); } //预处理 for(int i=1;i<=a-n+1;i++) { for(int j=1;j<=b;j++) { max_g[i][j]=min_g[i][j]=g[i][j]; for(int k=1;k<n;k++) { max_g[i][j]=max(max_g[i][j],g[i+k][j]); min_g[i][j]=min(min_g[i][j],g[i+k][j]); } } } for(int i=1;i<=a-n+1;i++) { deq1.clear(); deq2.clear(); for(int j=1;j<=b;j++) { //max_g[i][j],min_g[i][j]为队列新遇到的元素 while(deq1.size() && max_g[i][deq1.back()]<max_g[i][j]) deq1.pop_back(); deq1.push_back(j); while(deq2.size() && min_g[i][deq2.back()]>min_g[i][j]) deq2.pop_back(); deq2.push_back(j); while(deq1.size() && deq1.front()<=j-n) deq1.pop_front(); while(deq2.size() && deq2.front()<=j-n) deq2.pop_front(); if(j>=n) ans=min(ans,max_g[i][deq1.front()]-min_g[i][deq2.front()]); } } cout<<ans; Please AC }