题目

洛谷上的题目
Acwing上的题目

根据y总的一波分析，我们得出……公式就是一切……
所以，我要学会推公式……
推公式……
公式……

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; const int N = 1e5 + 10;
int n, m;
ll s[N]; 
ll f[N];
int q[N];
ll g(int i)
{return f[i - 1] - s[i];
}int main()
{scanf("%d%d", &n, &m);//以前缀和的形式进行保存for(int i = 1; i <= n; i ++){scanf("%lld", &s[i]);s[i] += s[i - 1];}//然后是单调队列优化着做//单调队列存储的是根据公式分析出来的那个关于变量j的式子，用子函数g()解决计算问题int hh = 0, tt = 0;for(int i = 1; i <= n; i ++){//头超出范围要弹出if(q[hh] < i - m) hh ++;//这里就是一个关于选与不选的故事了，要从一个蝙蝠讲起……f[i] = max(f[i - 1], g(q[hh]) + s[i]);while(hh <= tt && g(q[tt]) <= g(i)) tt --;//可以看出，q存储的是用公式推出来的那一坨……q[++ tt] = i;}printf("%lld\n", f[n]);return 0;
}