洛谷P2627 修剪草坪 题解 单调队列优化DP

题目链接：https://www.luogu.com.cn/problem/P2627

解题思路：

定义状态 \(f[i]\) 表示："前 \(i\) 只奶牛，且当 \(i < n\) 时，第 \(i+1\) 只奶牛不选"的情况下的最大值。

则，当 \(i \le k\) 时，

\[f[i] = \sum_{j=1}^{i} e[j]\]

当 \(i > t\) 时，

\[f[i] = \max_{j \in [i-k-1, i-1]}(f[j] + \sum_{x=j+2}^i e[x])\]

其中区间和我们可以额外开一个 sum 数组用于存储前缀和。

实现代码如下（TLE代码）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, k;
long long e[maxn], sum[maxn], f[maxn], ans;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> e[i];
        sum[i] = sum[i-1] + e[i];
    }
    if (k > n) k = n;
    for (int i = 1; i <= k; i ++) f[i] = sum[i];
    for (int i = k+1; i <= n; i ++)
        for (int j = 1; j <= k; j ++)
            f[i] = max(f[i], f[i-j-1] + sum[i] - sum[i-j]);
    for (int i = 1; i <= n; i ++)
        ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

但是这样的时间复杂度是 \(O(n \cdot k)\) 的，会超时。

于是考虑将上述的状态转移方程进行一下转化：

\[f[i] = \max_{j \in [i-k-1, i-1]}(f[j] - sum[j+1]) + sum[i]\]

所以考虑将 \(f[j] - sum[j+1]\) 放到一个单调队列当中。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, k;
long long e[maxn], sum[maxn], f[maxn], ans;
deque<int> que;
long long cal(int i) {
    return f[i] - sum[i+1];
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> e[i];
        sum[i] = sum[i-1] + e[i];
    }
    if (k > n) k = n;
    for (int i = 1; i <= k; i ++) f[i] = sum[i];
    int j = 0;
    for (int i = k+1; i <= n; i ++) {
        for (; j < i; j ++) {
            while (!que.empty() && cal(que.back()) <= cal(j)) que.pop_back();
            que.push_back(j);
        }
        while (que.front() < i-k-1) que.pop_front();
        f[i] = f[que.front()] - sum[que.front()+1] + sum[i];
    }
    for (int i = 1; i <= n; i ++)
        ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

然后我错了样例3，因为我一开始将 \(j\) 的初始坐标设为了 \(1\) ，后来改成了 \(0\) 就 AC 了。

可以拿下面这组测试数据试一下：

测试in

6 1
4
7
2
0
8
9

测试out

16

洛谷P2627 修剪草坪 题解 单调队列优化DP

原文：https://www.cnblogs.com/quanjun/p/12284548.html