Epi4any @ 2022-11-11 22:27:42
rt，萌新初学单调队列优化dp，样例总是过不了，不太会调试，求教（大佬轻喷qwq）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, k, e[maxn], f[maxn], sum;
deque<int> q;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> e[i], sum += e[i];
}
f[1] = e[1], q.push_back(1);
for (int i = 2; i <= n; i++) {
while (!q.empty() && q.front() <= i - k) q.pop_front();
if (!q.empty()) f[i] = f[q.front()] + e[i];
while (!q.empty() && f[q.back()] >= f[i]) q.pop_back();
q.push_back(i);
}
int mn = 2e9;
for (int i = n; i >= n - k + 1; i--) mn = min(mn, f[i]);
cout << sum - mn << endl;
return 0;
}by register_new @ 2022-11-11 22:34:11
凉了，下节课就要学这东西了
by whdywjd @ 2022-11-12 08:32:33
改成这样吧？
if (!q.empty()) f[i] = f[q.front()] + e[i];
while (!q.empty() && f[q.back()] >= f[i]) q.pop_back();
while (!q.empty() && q.front() <= i - k) q.pop_front();
q.push_back(i);by Epi4any @ 2022-11-13 08:16:40
@whdywjd 谢谢！
by Epi4any @ 2022-11-15 16:06:07
@whdywjd 但是似乎还不太对。。
by whdywjd @ 2022-11-15 17:22:07
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n, k, e[maxn], f[maxn], sum;
deque<int> q;
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> e[i], sum += e[i];
}
f[0] = 0, q.push_back(0);
for (int i = 1; i <= n; i++) {
while (!q.empty() && q.front() <= i - k - 1) q.pop_front();
if (!q.empty()) f[i] = f[q.front()] + e[i];
while (!q.empty() && f[q.back()] > f[i]) q.pop_back();
q.push_back(i);
}
int mn = 2e9;
for (int i = n; i >= n - k - 1 && i; i--) mn = min(mn, f[i]);
cout << sum - mn << endl;
return 0;
}以上代码有40分