算法

(DP,斜线型DP,堆) $O(n^2logn)$

状态表示：

• f[i]表示前i单位时间内可获取的最多金币数；
• s[i, j]表示从[i, j]开始向左上角走的路径上的金币数量之和，注意如果走到第一行，则跳至最后一行继续走；
• cost[i]表示从第i个点购买机器需要花费的金币数；

状态转移：

• f[i] = max{f[i - k] + s[j, i] - s[j - k, i - k] - cost[j - k + 1]}，其中1 <= k <= i, k <= p, 1 <= j <= n；

整理一下可得：

• f[i] = max{f[i - k] - s[j - k, i - k] - cost[j - k + 1]} + s[j, i]

我们令g[i, j] = f[i] - s[j, i] - cost[j + 1]，则：

• f[i] = max{g[i - k][j - k]} + s[j, i]，其中1 <= k <= i, k <= p, 1 <= j <= n；

其中有三个变量，需要 $O(n^3)$ 的计算量，因此需要优化。

我们发现状态转移方程是对长度为 $p$ 的滑动窗口求最大值，因此可以用单调队列或者堆可以去掉一重循环。

这里为了思路简单，我们选择堆来优化。

时间复杂度

总共两重循环，以及一重堆的操作，因此总时间复杂度是 $O(n^2logn)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

int n, m, p;
int s[N][N], cost[N];
int f[N], g[N][N];

struct Node
{
    int v, i, j;
    bool operator< (const Node& W) const
    {
        return v < W.v;
    }
};

priority_queue<Node> heap[N];

int get(int x)
{
    x %= n;
    if (x <= 0) x += n;
    return x;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (j == 1) s[j][i] += s[n][i - 1];
            else s[j][i] += s[j - 1][i - 1];

    memset(f, -0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    f[0] = 0;

    for (int i = 1; i <= n; i++) scanf("%d", &cost[i]);
    for (int i = 1; i <= n; i++)
    {
        g[0][i] = -cost[get(i + 1)];
        heap[get(0 - i)].push({ g[0][i], 0, i });
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            auto& h = heap[get(i - j)];
            while (h.size())
            {
                auto t = h.top();
                if (i - p > t.i) h.pop();
                else
                {
                    f[i] = max(f[i], s[j][i] + t.v);
                    break;
                }
            }
        }
        for (int j = 1; j <= n; j++)
        {
            g[i][j] = f[i] - s[j][i] - cost[get(j + 1)];
            heap[get(i - j)].push({ g[i][j], i, j });
        }
    }

    int res = 0;
    for (int i = 0; i <= m; i++) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}