P2627 修剪草坪

给你一个\(n\)个数字的数组，至多连续取\(k\)个数字，求取出的最大和。

预处理了前缀和之后，一维dp很容易想：\(dp[i] = max(dp[j-1] + sum[j+1,i])\)

用前缀和写就是\(dp[i]=max(dp[j-1]+sum[i]-sum[j])\)

把与\(i\)有关的拿出\(max\)，就有\(dp[i]=sum[i]+max(dp[j-1]-sum[j])\)

\(j\)能取的是一个固定区间，长度为\(k\)，所以直接单调队列维护咯！

维护一个单调递减的队列，队头就是最大值了。

复杂度为\(O(n)\)。太优美了！

代码：

/************************************************************************* @Author: Garen @Created Time : Tue 12 Feb 2019 10:19:25 AM CST @File Name: P2627.cpp @Description: ************************************************************************/#include
    
     #define ll long longconst ll maxn = 100005;ll dp[maxn];ll a[maxn], sum[maxn];ll n, k;std::deque
     
       q;ll d[maxn];ll update(ll i) {    d[i] = dp[i - 1] - sum[i];    while(!q.empty() && d[q.back()] < d[i]) q.pop_back();    q.push_back(i);    while(!q.empty() && q.front() < i - k) q.pop_front();    return d[q.front()];}int main() {    scanf("%lld %lld", &n, &k);    for(ll i = 1; i <= n; i++) {        scanf("%lld", &a[i]);        sum[i] = sum[i - 1] + a[i];    }    /*    for(ll i = 1; i <= k; i++) dp[i] = sum[i];    for(ll i = k + 1; i <= n; i++) {        for(ll j = i - k; j <= i; j++) {            dp[i] = std::max(dp[i], dp[j - 1] + sum[i] - sum[j]);        }        // dp[i] = sum[i] + std::max(dp[j - 1] - sum[j]));    }    */    q.push_back(0);    for(ll i = 1; i <= n; i++) {        dp[i] = sum[i] + update(i);    }    printf("%lld\n", dp[n]);    return 0;}