洛谷1070 道路游戏

题意

有形成环形的 $N$ 个机器人工厂，购买机器人的价格为 $V_i$ 。连接 $i\rightarrow i+1$ 的道路编号为 $i$ ，在时间 $j$ 的金币数为 $s[i][j]$ 。

每次可以在任意工厂购买一个机器人，机器人最多可以走 $P$ 条边，并收集边上的金币。不能同时存在多个机器人。求 $M$ 的时间内最多能收集多少金币。

$N,M\le 1000$ 。

题解

用 $f[i]$ 表示时间 $i$ 时最多收集的金币。$O(N^3)$ 枚举时间、起点、走的步数就可以过。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=2005;
int n,m,p,s[N][N],v[N],f[N];

signed main()
{
    n=read(); m=read(); p=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i][j]=read();
    for (int i=1;i<=n;i++) v[i]=read();
    memset(f,~0x3f,sizeof(f));
    f[0]=0;
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            int cur=f[i-1]-v[j]; //当前金币
            for (int k=1;k<=p && i+k-1<=m;k++)
            {
                int to=j+k-1; //到达的点
                if (to>n) to-=n;
                cur+=s[to][i+k-1];
                f[i+k-1]=max(f[i+k-1],cur);
            }
        }
    }
    return !printf("%d",f[m]);
}