动态规划($O(n^3)$)

状态表示：

$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；$

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,p;
int gold[N][N];
// gold[i][t] 表示第i条道路，时间为t的时候的金币数目
int cost[N];
//cost[i] 表示第i条道路需要购买机器需要的数目
int f[N];
//f[i]表示时间为i的时候一共可以获得多少金币
int main()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) //获取道路和金币
    {
        for(int t=1;t<=m;t++)
        {
            cin>>gold[i][t];
        }
    }
    for(int i=1;i<=n;i++) cin>>cost[i]; //获取每条道路需要购买机器人需要的金币
    memset(f,-0x3f,sizeof f); //无穷小
    f[0]=0; //起点
    for(int t=1;t<=m;t++) //枚举每个时刻
    {
        for(int i=1;i<=n;i++) //枚举当前的机器人在哪条道路上
        {
            int tmp=0;
            for(int k=1;k<=p;k++) //枚举步数
            {
                int r=i-k+1; //起点道路
                if(r<1) r+=n; //如果走完一圈了
                int time=t-k+1; //起点时间
                if(time>=1) //有效时间
                {
                    tmp+=gold[r][time]; //累加起点时间
                    f[t]=max(f[t],tmp-cost[r]+f[time-1]); //更新从起点到当前距离的最大值
                }
            }
        }
    }
    cout<<f[m];
    return 0;
}

【算法分析2】 通过观察，我们可以比较容易得到在第三层循环里面状态转移方程是对长度为$p$的滑动窗口的最大值，可以用单调队列或者是堆来优化。

#include<bits/stdc++.h>
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()
{
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>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++) cin>>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]
        {
            g[i][j]=f[i]-s[j][i]-cost[(get(j+1))];
            heap[get(i-j)].push({g[i][j],i,j});
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

5 8 8
92 99 72 43 43 53 44 26
28 4 12 26 12 38 37 48
81 37 69 87 60 45 90 31
28 78 37 29 89 77 49 61
77 4 66 19 61 99 90 89
75 74 43 89 87

522