Z3k7223 @ 2024-04-09 13:52:51
这份代码的初始化是 head = 1, tail = 0 (样例没过),但是提交喜提 10pts,只要把初始化改为 head = 1, tail = 1 就能 AC,求问原因,玄关感谢。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k;
int a[N], sum[N], f[N][2];
int p[N], q[N], head = 1, tail;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = q[head] + sum[i];
while (head <= tail && q[tail] < f[i][0] - sum[i]) {
--tail;
}
q[++tail] = f[i][0] - sum[i];
p[tail] = i;
while (head <= tail && p[head] < i - k + 1) {
++head;
}
}
cout << max(f[n][0], f[n][1]) << '\n';
return 0;
}
by zzxLLL @ 2024-04-09 14:56:01
其他点应该可以从