修建草坪

原题链接

题目描述

给定一个长度为 \(n\) 的数组 \(w\)，其中 \(w_i\) 是第 \(i\) 个元素的 贡献

我们可以选择的 数组 中的一些 元素，这些元素的 贡献总和 表示我们该种 方案 的 价值

但是，如果方案中出现选择了 连续相邻 且超过 \(m\) 个元素，则这些 连续相邻 的元素 贡献 归零

求解一种 方案，使得选择的 元素贡献总和 最大

---

思路

动态规划 dp[i]

集合： 在前 \(i\) 头牛里面选，且合法(即区间长度不超过m)的贡献集合

属性： 最大值

状态计算： 对于 \(dp[i]\)，有两种选择

1. 不选择第 \(i\) 头牛，易知，等价于 \(dp[i-1]\)

2. 选择第 \(i\) 头牛，\(dp[i]=\max\{dp[j-1]+s[i]-s[j]\}_{(0\le i-j\le m)}\)

   整理上式可得 \(dp[i]=s[i]+\max\{dp[j-1]-s[j]\}_{(i-m\le j\le i)}\)，即求区间 \([i-m,i]\) 内，\(dp[j-1]-s[j]\) 的最大值

综上所述，dp状态转移方程即为：

\[dp[i]=\max\{dp[i-1],s[i]+\max\{dp[j-1]-s[j]\}_{(i-m\le j\le i)}\}\]

代码

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

typedef long long LL;

const int N = 100010;

int n, m;
LL s[N], dp[N];
int q[N];

LL g(int i) {
    return dp[i - 1] - s[i];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i++) {
        if (i - m > q[hh]) hh++;
        dp[i] = max(dp[i - 1], s[i] + g(q[hh]));
        while (hh <= tt && g(q[tt]) <= g(i)) tt--;
        q[++tt] = i;
    }

    cout << dp[n] << endl;

    return 0;
}