感觉是一道很好的单调队列优化DP

首先 O(n3)O(n^3) 的朴素DP很好想

令 fif_i 表示前 ii 获得金币的最大值,不难的出状态转移方程

fi=max⁡1≤j≤p(fi−k−costi−k+vali−k−>i)f_i=\max\limits_{1\le j\le p}(f_{i-k}-cost_{i-k}+val_{i-k->i})

valval 的求法可以通过维护一个对角线上的前缀和,我们先将道路的权值转化为点的权值,

即转化到道路终点上,为了方便,我们让工厂的编号从0开始,这样就可以通过取模直接表述出走之前的点

这样就可以写出朴素版的DP

for (int i = 1; i <= m; i++)
    for (int j = 0; j < n; j++)
         for (int k = 1; k <= min(p, i); k++)
             f[i] = max(f[i - k] + sum[i][j] - sum[i - k][j - k] - c[j - k], f[i]);

这到题到这里就已经可以AC了,但如何数据严格的话,O(n3)O(n^3) 肯定是不能过的,

想办法省略掉第三维,让上面的转移方程稍微变形一下得到

fi=max(fi−k−sumi−k,j−k−cj−k)+sumi,jf_i=max(f_{i-k}-sum_{i-k,j-k}-c_{j-k} )+sum_{i,j}

令 gi,j=fi−sumi,j−cjg_{i,j}=f_i-sum_{i,j}-c_j

fi=max(gi−k,j−k)+sumi,jf_i=max(g_{i-k,j-k})+sum_{i,j}

可以看出 gi−k,j−kg_{i-k,j-k} 其实就是对角线上的值,对于每一个对角线,可以开一个单调队列来维护

每一个点所对应的对角线的编号 (j−i+n)%n(j-i+n)\% n,具体实现看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define get(i, j) (f[i] - sum[i][j] - c[j])
using namespace std;
const int N = 1005;

int l[N], r[N], q[N][N], pos[N][N];
int sum[N][N], val[N][N], g[N][N], c[N], f[N];

int main()
{
    int n, m, p;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &val[i % n][j]);//将道路带来的收益交给点
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < n; j++)
            sum[i][j] = sum[i - 1][(j - 1 + n) % n] + val[j][i];//处理对角线上的前缀和
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &c[i]);
        q[i][r[i]] = -c[i];//初始化单调队列
    }
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int id = ((j - i) % n + n) % n;
            while (l[id] <= r[id] && pos[id][l[id]] + p < i)
                l[id]++;
            if (l[id] <= r[id])
                f[i] = max(f[i], q[id][l[id]] + sum[i][j]);
        }//更新答案
        for (int j = 0; j < n; j++)
        {
            int id = ((j - i) % n + n) % n;
            while (l[id] <= r[id] && q[id][r[id]] <= get(i, j))
                r[id]--;
            q[id][++r[id]] = get(i, j);
            pos[id][r[id]] = i;//记录一个位置,以判断是否合法
        }//更新单调队列
    }
    printf("%d", f[m]);
    return 0;
}