I 九峰与分割序列

其他题目题解点击此处

思路

求一种分割方法使得所有子区间的贡献之和最大，我们设为到为止所有子区间的最大贡献和，为到为止最后最后一段区间长度大于k的所有贡献之和。

那么就会有动态转移方程：

上部分为不分割，因为只是加一倍的原来的那段区间和，那么它的值也就是相当于当前的值加上前面那一段，下部分为符合分割条件可以分割，就是取可以分割的区间乘以2加上前面那一段。

的状态转移好理解，就是让后面k + 1个数取一倍，剩下的数取最大即可。

继续优化，看能不能将dp的转移方程的第二个条件的给优化一下。
因为它的长度永远都是只能小于等于的，所以可以想到滑动窗口，也就是单调队列。
让单调队列维护 的最大值，每次取队首就是最大值。
单调队列基础知识就不讲了，代码中有一个弹出队列的细节在这里讲一下。

while (hh <= tt && 2 * S(q[tt] + 1, i) + f[q[tt]] < f[i]) --tt; 为什么是小于？
因为如果把i放入队列的值就会变成2 * S(i+ 1, i) + f[i] 也就是。

代码中维护的是 个下标。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
int n, k;
ll dp[N], f[N], c[N];
int a[N], q[N];

ll S(int l, int r)
{
    return c[r] - c[l - 1];
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin >> n >> k;
    _rep(i, 1, n)
    {
        cin >> a[i];
        dp[i] = f[i] = c[i] = c[i - 1] + a[i];
    }

    int hh = 0, tt = -1;
    q[++tt] = k + 1;
    _rep(i, k + 2, n)
    {
        while (hh <= tt && i - q[hh] > k) ++hh;
        dp[i] = max(2 * S(q[hh] + 1, i) + f[q[hh]], dp[i - 1] + a[i]);
        f[i] = dp[i - k - 1] + S(i - k, i);
        while (hh <= tt && 2 * S(q[tt] + 1, i) + f[q[tt]] < f[i]) --tt;
        q[++tt] = i;
    }

    cout << dp[n] << endl;
    return 0;
}