题目地址：洛谷：【P1070】道路游戏 – 洛谷

题目描述

小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有 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 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：

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

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

输入输出样例

输入样例#1：

2 3 2 
1 2 3 
2 3 4 
1 2

输出样例#1：

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。
NOIP 2009 普及组 第四题

题解

这里我采用的是GhastIcon同学的思路。可以在这里P1070 道路游戏 题解找到他的题解。

最初的想法

设计状态dp[i]为到第i时刻获得的最大金币数，转移可以通过枚举这个时刻到的位置和走过的步数来实现，方程如下
dp[i] = \max \{dp[i - t] + g[i][s - 1] - g[i][s - t - 1] - c[s - t]\}
具体解释一下上面的各个变量。t是枚举的步数，s是枚举的当前位置。i-t表示t时间前的时刻，p-t表示t时间前的位置（要注意处理一下让它在1~n范围内），g表示一种斜线的前缀和，c表示在这个位置买机器人的开销。可以知道我们的收益在题目给的那个表上是对角线上计算的，以样例为例，两种斜线前缀和如下图。

由此我们知道这个DP是O(mn^2)的。这种思路对于这道题来说不够优。我们需要优化。

降低时间：单调队列

整理一下DP方程。
dp[i] = \max \{dp[i - t] - g[i][s - t - 1] - c[s - t]\} + g[i][s - 1]
我们发现max标记里面的这个值其实可以单调队列处理，因为枚举的t有一个范围1 \leq t \leq p。设一个 h[i][j] = dp[i] - g[i][j - 1] - c[j] ，用h代换方程中的max里面的部分，单调队列维护的就是这个h。对于h的每一个j创建单调队列，在更新i的同时更新单调队列，这样就可以达到降低时间复杂度的目的。转移变为O(n)。
这里的思路去发现依赖关系和最值转移关系。

其他优化？

感觉dp数组都可以拿掉了，因为最后dp出来的值都是要插入单调队列里面的。可以稍稍优化空间常数。

实现细节

初始值要设成买一个机器人的开销。以及我代码中的deque可以全换成手写双端队列，STL比较慢。

代码

// Code by KSkun, 2018/2 
#include <cstdio>
#include <cstring>
#include <deque>
#include <utility>
typedef std::pair<int, int> PI;

std::deque<PI> que[1005];
int n, m, p, sum[1005][1005], cost[1005], dp[1005], v;

inline int minus(int a, int b) { // return a - b
    return ((a - b) % n + n) % n;
}

int main() {
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &sum[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &cost[i]);
    }
    // 处理对角线前缀和 
    for(int i = 2; i <= m; i++) {
        for(int j = 0; j < n; j++) {
            sum[j][i] += sum[minus(j, 1)][i - 1];
        }
    }
    // 设置初值表示开始一定要买一个机器人 
    for(int i = 0; i < n; i++) {
        que[minus(i, -1)].push_back(std::make_pair(-cost[i], 0));
    }
    memset(dp, 0xc0, sizeof dp);
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < n; j++) {
            dp[i] = std::max(dp[i], que[minus(j, i - 1)].front().first + sum[minus(j, 1)][i]);
        } 
        for(int j = 0; j < n; j++) {
            while(!que[minus(j, i - 1)].empty() && i - que[minus(j, i - 1)].front().second >= p) {
                que[minus(j, i - 1)].pop_front();
            }
            v = dp[i] - sum[minus(j, 1)][i] - cost[j];
            while(!que[minus(j, i - 1)].empty() && que[minus(j, i - 1)].back().first <= v) {
                que[minus(j, i - 1)].pop_back();
            }
            que[minus(j, i - 1)].push_back(std::make_pair(v, i));
        }
    }
    printf("%d", dp[m]);
    return 0;
}