P2627 [USACO11OPEN]Mowing the Lawn G

$70pts$ 费用流做法：

查看代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
typedef long long LL;
typedef pair <LL, int> PLI;
const int N = 1e5 + 10, M = 4e5 + 10;
const LL inf = 1e14;
bool vis[N];
int n, k, st, ed, pre[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M];
LL d[N], h[N], cst[M];
void spfa()
{
    for (int i = st; i <= ed; i++)
        h[i] = -inf;
    queue<int> q;
    q.push(st);
    vis[st] = true;
    h[st] = 0;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && h[t] + cst[i] > h[edg[i]])
            {
                h[edg[i]] = h[t] + cst[i];
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
}
bool dijkstra()
{
    for (int i = st; i <= ed; i++)
        vis[i] = false, d[i] = -inf;
    priority_queue<PLI> q;
    d[st] = 0;
    q.push(make_pair(0, st));
    while (!q.empty())
    {
        int t = q.top().second;
        q.pop();
        if (vis[t])
            continue;
        vis[t] = true;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && d[t] + cst[i] + h[t] - h[edg[i]] > d[edg[i]])
            {
                d[edg[i]] = d[t] + cst[i] + h[t] - h[edg[i]];
                pre[edg[i]] = i;
                q.push(make_pair(d[edg[i]], edg[i]));
            }
    }
    return d[ed] ^ -inf;
}
LL PrimalDual ()
{
    spfa();
    LL res = 0;
    while (dijkstra())
    {
        for (int i = st; i <= ed; i++)
            h[i] += d[i];
        int t = k;
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            t = min(t, wt[pre[i]]);
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            wt[pre[i]] -= t, wt[pre[i] ^ 1] += t;
        res += t * h[ed];
    }
    return res;
}
void add(int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    cst[idx] = d;
}
int main()
{
    read(n), read(k);
    st = 0, ed = n + 1;
    for (int i = st; i <= ed; i++)
        hd[i] = -1;
    for (int i = 1; i <= ed; i++)
    {
        add(i - 1, i, k, 0);
        add(i, i - 1, 0, 0);
    }
    for (int i = 1, a; i <= n; i++)
    {
        read(a);
        add(i, min(ed, i + k + 1), 1, a);
        add(min(ed, i + k + 1), i, 0, -a);
    }
    write(PrimalDual());
    return 0;
}

考虑DP，$f _ i$ 表示选择 $i$ 和之前的可以取得的最大值，不能取超过 $k$ 个连续的数，这意味着在选择第 $k + 1$ 个数的时候，需要从其中选择一处断开，即可得到转移方程：$f _ i = \max _ {k = i - m} ^ {i - 1} f _ {k - 1} + w_{k + 1} + w _ {k + 2} + \ldots + w[i]$ 。

前缀和一下：$f _ i = \max _ {k = i - m} ^ {i - 1} f _ {k - 1} + s _ i - s _ k$ 。

其中 $s _ i$ 与转移无关，即 $f _ i = (\max _ {k = i - m} ^ {i - 1} f _ {k - 1} - s _ k) + s _ i$ ，可看做一个长度为 $m$ 的滑动窗口，用单调队列解决。

注意开始的时候，有从 $0$ 断开的情况，不方便操作，单独将 $1\ldots m$ 部分处理。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int hd = 1, tl = 0, q[N];
int n, m;
LL s[N], f[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, a; i <= n; i++)
    {
        scanf("%d", &a);
        s[i] = s[i - 1] + a;
    }
    for (int i = 1; i <= m; i++)
    {
        while (hd <= tl && f[q[tl] - 1] - s[q[tl]] <= f[i - 1] - s[i])
            tl--;
        q[++tl] = i;
        f[i] = s[i];
    }
    for (int i = m + 1; i <= n; i++)
    {
        while (hd <= tl && q[hd] < i - m)
            hd++;
        while (hd <= tl && f[q[tl] - 1] - s[q[tl]] <= f[i - 1] - s[i])
            tl--;
        q[++tl] = i;
        f[i] = f[q[hd] - 1] - s[q[hd]] + s[i];
    }
    LL res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, f[i]);
    printf("%lld", res);
    return 0;
}