xyxyfqbj @ 2020-04-11 13:47:18
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL s[N], sum = 0, f[N];
int n, m, q[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
sum += s[i];
}
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++)
{
while (hh <= tt && i - q[hh] > m + 1) hh++;
f[i] = f[q[hh]] + s[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt--;
q[ ++ tt] = i;
}
LL res = 0x7fffffff;
for (int i = n - m; i <= n; i++)
{
res = min(res, f[i]);
}
cout << sum - res << endl;
return 0;
}
WA在第8个点了
by 㔿㕛㠪䦹冎 @ 2020-08-21 17:10:27
res 初始值不够大
by _l_l_l_l_l_ @ 2021-08-04 18:38:55
@xyxyfqbj 建议res开到1e16
by william_zy @ 2022-11-19 20:16:26
可以试着强行推 f[n+1]
,输出 sum-f[n+1]
?我就是这么莫名