本题就是让我们求一个长度不大于m的最大子序和
设$sum_{i}$为前$i$个数的前缀和
容易列出状态转移方程
$ans=\max \limits_{i \le n} \lbrace {sum_i-\min\limits_{i-m \le j \le i}\lbrace sum_j \rbrace }\rbrace$
但如果暴力枚举,时间复杂度是$O(nm)$的
考虑用单调队列进行优化
不妨比较任意两个位置$j_{1}, j_{2}$, 如果 $j_{1} < j_{2} , sum_{j_{1}} \ge sum_{j_{2}}$, 那么$j_{1}$就是无用决策
因为$j_{1}$能取到的地方,$j_{2}$也能取到,所以
$j_{1}$永远不会成为最优决策
综上所述,我们维护一个下标位置递增,对应前缀和sum也递增的单调队列
, 只有这个队列中的决策,才有可能成为最优决策。
我们对每个$i$每次执行三个步骤
1.判断队头决策与$i$的距离是否超出$m$的范围,若超出则出队
2.此时队头就是右端点为$i$时,左端点$j$的最优选择
3.不断删除队尾决策,直到队尾对应的$sum$值小于$sum_{i}$。最后把$i$作为一个新的决策入队
#include<bits/stdc++.h>
using namespace std;
char buf[100010], *p1, *p2;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++
template<class item>
inline item read() {
item res = 0;
bool negative = 0;
char ch = getchar();
while (!isdigit(ch)) negative |= ch == '-', ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return negative ? -res : res;
}
template<class item>
inline item read(item & t) {
t = read<item>();
return t;
}
#define max(a, b) (!((a) < (b)) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
read(t), read(args...);
}
//快读,长了点
int sum[500010], n, q[500010], m, ans = -1e9;
int main() {
cin >> n >> m;
for (register int i = 1; i <= n; ++i) read(sum[i]), sum[i] += sum[i - 1];
int l = 1, r = 1;
for (register int i = 1; i <= n; ++i) {
while (l <= r && q[l] < i - m) ++l;//排除不可能决策
ans = max(ans, sum[i] - sum[q[l]]);
while (l <= r && sum[q[r]] >= sum[i]) --r;//排除无用决策
q[++r] = i;//插入新决策
}
cout << max(ans, 0);//被这个坑了,好像可以什么也不选
}
最后还是提醒大家多到我的博客看题解,多点几个赞
大佬,请问为什么这里的tail是从0开始呢?如果从-1开始就会错....
我不是从一开始吗?表示加入了 0 这个决策。从 -1 开始应该数组会越界吧
$\lbrace$
$\{$
抄书上的步骤,字都一样的
头像 + 名字瞩目
这个名字挺好的
$\underbrace{1212}_{212}$