【正经题解】道路游戏

用一维数组f储存第i秒能获得的最大钱数

因为最多同时存在1个机器人

第i秒时第j个机器人走k次(1<=k<=p)

f[i]=max(f[i],f[i-k]-pay[last]+sum)

这里是从当前点倒推

last是上一个点

当last=0,last=n

sum要一遍遍加上钱k秒第last路上的金币数

每次减去第last条道路（即第last个工厂机器人）的价格

如果i-k<0

直接退出k循环，时间不为负

因为结果可能是负的

初始化为-99999999

f[0]=0，即第0秒金币数为0

输出第m秒的值

# include<iostream>
# include<cstring>
using namespace std;
int n,m,p;
int pay[1001];
int money[1001][1001];
int f[1001];
int main()
{
    cin>>n>>m>>p;
    memset(f,-999999,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        cin>>money[i][j];
    for(int i=1;i<=n;i++)
      cin>>pay[i];
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++)
        {
            int ff=j-1;
            if(!ff) ff=n;
            int ss=money[ff][i];
            for(int k=1;k<=p;k++)
              {
                  if(i-k<0) break;
                  f[i]=max(f[i],f[i-k]+ss-pay[ff]);
                  ff--;
                  if(!ff) ff=n;
                  ss+=money[ff][i-k];
              }
        }
    cout<<f[m];
    return 0;
}