参考算法学习笔记(66): 单调队列 - 知乎 (zhihu.com)
题目描述
给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。
输入格式
第一行两个整数n，k
以下n行，每行一个整数表示a[i]。
输出格式
输出一个值表示答案。
样例
样例输入
5 2
1
2
3
4
5
样例输出
12
提示
对于20%的数据，n <= 10
对于另外20%的数据， k = 1
对于60%的数据，n <= 1000
对于100%的数据，1 <= n <= 100000，1 <= k <= n，0 <= 数字大小 <= 1,000,000,000
时间限制500ms
转换思路：选数的最大和--->删数的最小和
先思考朴素的dp
先设状态，设dp[i]为删掉a[i]时的最小和。
可以列出方程，apparently~
\[dp_i = \begin{cases} a_i,\ i\le k+1\\ \min\limits_{i-k-1\le j \le i-1} dp_j + a_i , i>k+1 \end{cases} \]于是，朴素dp便可以写出。
#include <bits/stdc++.h>
#define rei register int
#define LL long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cvar int n, m, T;
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, LL mod){long long res = 1; while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1; } return res;}
using namespace std;
const int maxn = 110010;
int n, k;
LL a[maxn];
LL f[maxn]; // 状态，f[i]表示为删去第i个数，的最小和！最小和，问题转化
int main()
{
LL sum = 0;
n = read(), k = read();
rep (i, 1, n, 1) {
a[i] = read();
sum += a[i];
}
rep (i, 1, n, 1)
{
// 处理f[i]
if (i <= k+1)
f[i] = a[i];
else {
LL mm = INF;
rep (j, i - k - 1, i - 1, 1) {
mm = min(mm, f[j] + a[i]);
}
f[i] = mm;
}
}
LL mm = INF;
rep (i, n - k , n, 1)
mm = min(mm, f[i]);
cout << sum - mm << endl;
return 0;
}
这道题卡的不是很死，可以拿到80分的好成绩。
那么考虑优化，使用单调队列优化最小值，在dp过程中O(1)求最值，顺带维护队列。
#include <bits/stdc++.h>
#define rei register int
#define LL long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cvar int n, m, T;
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, LL mod){long long res = 1; while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1; } return res;}
using namespace std;
LL n, k, sum = 0;
int main()
{
cin >> n >> k;
vector<LL>a(n + 1), dp(n + 1);
rep (i, 1, n, 1) {
a[i] = read();
sum += a[i];
}
deque<LL>Q;
rep (i, 1, n, 1)
{
if (i > k + 1)
dp[i] = dp[Q.front()] + a[i];
else
dp[i] = a[i];
// 更新单调队列
if (!Q.empty() && i - Q.front() >= k + 1)
Q.pop_front();
while (!Q.empty() && dp[Q.back()] > dp[i])
Q.pop_back();
Q.push_back(i);
}
cout << sum - *min_element(dp.end() - k - 1, dp.end()) << endl;
return 0;
}
（这题记得开龙龙）
重点需要讲解的，不过就是更新单调队列的部分。
这道题的单调队列存储的是下标，但是根据dp数组的值进行维护。
维护具体是这样的：
如果当前队列队首值（队列值当然就是dp的下标）距离i超过了k，说明连续数字超过了k个，则这个点不能要。由于每一次i++都会判断一次是否大于k，所以第一个维护pop_front()只需要if，不需要while；
第二个while完全是为了push_back(i)做准备的，因为我们一定要push_back(i)进去，又要为了维护单调性，所以不得不剔除队尾的元素们。
P2627 双倍经验，同样代码可过
标签：P2034,ch,队列,res,int,dp,define From： https://www.cnblogs.com/CYLSY/p/16815949.html