传送门

给定N个数，代表N个景点的权值，必须顺序参观完。每天最多参观K个景点，但是必须严格N/K+(N%K!=0)天参观完。当天的收获为当天景点的最大权值，问总收获最大是多少。
N和K都小于1E6

先考虑这样一种状态表示：
如果把每K个景点分成一份，最后一份可能会少K-N%K个。记为M。
假设每天的目标是一份。
f[i][j] 表示前 i 天偷了 j 天懒。也就是说本来应该走i * k 个景点，但是只走了i * k – j个。
很明显只要确定了偷懒天数，第x天停留的位置就固定了。所以第二维也可以换为停留的位置。
假设停留在下图的i点。
很明显f[x][i]=\max\limits_{j=i-k \to st} (f[x-1][j]+\max\limits_{k=j\to i}a[k])

由于每个阶段都是固定长度，所以很好判断当i%k==0的时候肯定是一个阶段的结束。
这样可以把dp状态优化到一维。

然后由于dp[j]+maxA[j+1,st]这一部分是不变的，可以在每个阶段结束的时候预处理出来。
用树状数组维护这个值的后缀区间最大。同时mxdp[x]记录dp[x,st]最大值和mxA[x]记录A[x+1,st]的最大值。下一个阶段可以直接使用。

当下一个阶段开始的时候，让a[i]和mxA[j]进行比较，如果a[i]更大，那么更新[j,i]的树状数组。同时j往后退。

当i向前移动一步的时候，同样也是更新[j,i]的树状数组。

次数树状数组[j,i]的最大值就是dp[i]的值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 233;
ll c[maxn], dp[maxn], mxdp[maxn];
void update(int i, ll val)
{
    for(int x = maxn - i - 1; x < maxn; x += x & -x) c[x] = max(c[x], val); 
}
ll suffixAsk(int i)
{
    ll ret = 0;
    for(int x = maxn - i - 1; x; x -= x & -x) ret = max(ret, c[x]);
    return ret;
}
int day[maxn], a[maxn];
int ma[maxn]; // max suffix a[] value of prevoius day
int n, k;
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = n%k, j = 1; i <= n; i += k) day[j++] = i;
    for(int i = 1, today = 1, back = 0, _maxa = 0; i <= n; i++)
    {
        int lim = day[today - 1];
        _maxa = max(a[i], _maxa);
        while(ma[back] <= _maxa && max(lim, i - k) <= back)
        {
            ma[back] = a[i];
            update(back, mxdp[back] + a[i]);
            if(ma[back - 1] <= _maxa && max(lim, i - k) <= back - 1) back--;
            else break;
        }
        if(max(lim, i - k) > back)
        {
            update(back + 1, mxdp[back + 1] + (ma[back + 1] = _maxa));
            back++;
        }
        dp[i] = suffixAsk(max(lim, i - k));
        if(i % k == 0)
        {
            int max2 = 0;
            for(int j = i; j >= max(day[today], i - k); j--)
            {
                //ma[j] = max(ma[j + 1], a[j]);
                //update(j, dp[j] + ma[j + 1]);
                update(j, dp[j] + (ma[j] = max2));
                max2 = max(max2, a[j]);
                mxdp[j] = max(mxdp[j + 1], dp[j]);
            }
            today++;
            back = i;
            _maxa = 0;
        }
    }
    cout << dp[n] << endl;
}