思路

经过长时间琢磨题解之后，我理解了dalao们的想法。这道题使用一维即可，但是O（n^3）的时间复杂度确实惊人。奈何我太菜了，只能理解这一种，那我也就只能来写写n^3的题解了。

转移方程：F[i] = max(F[i], F[i-k] + sum – cost[curt]，其中i表示当前的时间，k表示目前设置的机器人的步数，sum代表累积起来的金币，curt表示当前机器人的编号。其中当curt = 0时，curt需要被设置成n（环形特征）。答案储存在F[m]。

代码

// P1070.cpp
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 2020;
int table[maxn][maxn];
int cost[maxn];
int F[maxn];
int n, m, p;

int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> table[i][j];
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    fill(F, F + maxn, -(1e9));
    F[0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            int curt = j - 1;
            if (curt == 0)
                curt = n;
            int sum = table[curt][i];
            for (int k = 1; k <= p; k++)
            {
                if (i - k < 0)
                    break;
                F[i] = max(F[i], F[i - k] + sum - cost[curt]);
                curt--;
                if (curt == 0)
                    curt = n;
                sum += table[curt][i - k];
            }
        }
    cout << F[m];
    return 0;
}