难度：提高+/省选-

题目描述

        小新正在玩一个简单的电脑游戏。
        游戏中有一条环形马路，马路上有n个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n个机器人工厂编号为1~n，因为马路是环形的，所以第 n个机器人工厂和第1个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这n段马路也编号为1~n，并规定第i段马路连接第i个机器人工厂和第i+1个机器人工厂（1≤i≤n-1），第n段马路连接第n个机器人工厂和第1个机器人工厂。

        游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在i（1≤i≤n）号机器人工厂购买了一个机器人，这个机器人会从i号机器人工厂开始，顺时针在马路上行走，第一次行走会经过i号马路，到达i+1号机器人工厂（如果 i=n，机器人会到达第1个机器人工厂），并将i号马路上的所有金币收集给小新。 游戏中，环形马路上不能同时存在2个或者2个以上的机器人，并且每个机器人最多能够在环形马路上行走p次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为1~p之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。

以下是游戏的一些补充说明：

  • 游戏从小新第一次购买机器人开始计时。
  • 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
  • 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
  • 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
  • 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。

        现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过m个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。

输入输出格式

输入格式：

        第一行3个正整数n,m,p意义如题目所述。
        接下来的n行，每行有m个正整数，每两个整数之间用一个空格隔开，其中第i行描
        述了i号马路上每个单位时间内出现的金币数量（1≤金币数量≤100），即第i行的第j（1≤j≤m）个数表示第j个单位时间内i号马路上出现的金币数量。
        最后一行，有n个整数，每两个整数之间用一个空格隔开，其中第i个数表示在i号机器人工厂购买机器人需要花费的金币数量（1≤金币数量≤100）。

输出格式：

        共一行，包含1个整数，表示在m个单位时间内，扣除购买机器人
        花费的金币之后，小新最多能收集到多少金币。

输入输出样例

Sample input

2 3 2
1 2 3
2 3 4
1 2

Sample output

5

说明

【数据范围】
        对于 40%的数据，2≤n≤40,1≤m≤40。
        对于 90%的数据，2≤n≤200,1≤m≤200。
        对于 100%的数据，2≤n≤1000,1≤m≤1000,1≤p≤m。

题解

        一道很有趣的题目，考察动态规划。这里介绍一种O(n3)的做法，本以为会TLE，但是由于某些原因（数据太水），导致这种方法也是可以AC的。
        思路就是规定dp(x)为x时刻开始购置一个机器人，到游戏结束可以得到的最多金币数。这样写的状态转移方程十分复杂。转移时遍历所有可能的购置和选择步数的方案，结合机器人的价格，进行之后时间状态的转移，取最大值。
        遍历是一件特别低效的做法。但是可以注意到dp(x)只能转移到dp(x+k)（1≤k≤p），每一个转移都固定了步数，只是选择哪一个机器人不定。可以开一个数组记录这个量，从而加快速度。
        所以开一个T数组记录第t时刻，设置步数为x时可以得到的最大金币收益（实质上就是机器人的选择）。求这个金币收益可以用矩阵的对角前缀和加速。再来点inline和读入优化黑魔法这题就A了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>

#define N 1000
#define inf 1e8
using namespace std;
int op[N][N], dp[N], T[N][N], n, m, p, sum[N][N] = {0}, value[N];

inline int solve(int t, int a, int b) {
    int s = 0;
    if (t && a)s = sum[a - 1][t - 1];
    if (a + b - 1 < n) return sum[a + b - 1][t + b - 1] - s;
    return sum[n - 1][t + n - 1 - a] - s + sum[(a + b - 1) % n][t + b - 1];
}

inline int f(int t, int x) {
    if (T[t][x] > -1e7)return T[t][x];
    for (int i = 0; i < n; i++)T[t][x] = max(T[t][x], solve(t, i, x) - value[i]);
    return T[t][x];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> p;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> op[i][j];
            if (!i || !j)sum[i][j] = op[i][j];
        }
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= p; j++)T[i][j] = (int) (-inf);
    }
    for (int i = 0; i < n; i++)cin >> value[i];
    for (int i = 1; i < m; i++) {//求对角前缀和
        for (int j = i; j < m; j++)sum[i][j] = sum[i - 1][j - 1] + op[i][j];
        for (int j = i + 1; j < n; j++)sum[j][i] = sum[j - 1][i - 1] + op[j][i];
    }
    dp[m] = 0;
    for (int i = m - 1; i >= 0; i--) {//时刻
        dp[i] = (int) (-inf);
        for (int j = 1; j <= m - i && j <= p; j++)dp[i] = max(dp[i], f(i, j) + dp[i + j]);
    }
    cout << dp[0];
    return 0;
}