小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有 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 个单位时间内，扣除购买机器人
花费的金币之后，小新最多能收集到多少金币。
2 3 2 1 2 3 2 3 4 1 2
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 普及组 第四题
（1）.O（n3）暴力
暴力的感觉：
很好想暴力，搞笑的是，我的暴力程序过了
笑容满面
设dp[i][k][j] = 第i个单位时间后，在第j个工厂，机器人行走了k步的最多金币
a[j][i]第i个单位时间，j路段的金币
b[j]工厂j买机器人的费用
要爆空间，我知道
i滚动一下就好
当k等于1的时候比较特殊，就是新买一个机器人，用上一个单位时间中所有方案中最大的一个减去买机器人的钱，加上这一个单位时间在j位置的金币
当k大于1的时候就好办了;
int pre = j - 1;
if(!pre) pre = n;
dp[i][k][j] = dp[i-1][k-1][pre] + a[pre][i];
代码
1 /********************** 2 User：Mandy.H.Y 3 Language:c++ 4 Problem:luogu1070 5 Algorithm: 6 Date: 2019.8.27 7 **********************/ 8 9 #include<bits/stdc++.h> 10 #define Max(x,y) ((x) > (y) ? (x) : (y)) 11 12 using namespace std; 13 14 const int maxn = 1005; 15 16 int n,m,p; 17 int a[maxn][maxn]; 18 int b[maxn]; 19 int dp[3][maxn][maxn]; 20 21 template<class T>inline void read(T &x){ 22 x = 0;bool flag = 0;char ch = getchar(); 23 while(!isdigit(ch)) flag |= ch == ‘-‘,ch = getchar(); 24 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar(); 25 if(flag) x = -x; 26 } 27 28 template<class T>void putch(const T x){ 29 if(x > 9) putch(x / 10); 30 putchar(x % 10 | 48); 31 } 32 33 template<class T>void put(const T x){ 34 if(x < 0) putchar(‘-‘),putch(-x); 35 else putch(x); 36 } 37 38 void file(){ 39 freopen("testdata.in","r",stdin); 40 // freopen("1070.out","w",stdout); 41 } 42 43 void readdata(){ 44 read(n);read(m);read(p); 45 for(int i = 1;i <= n; ++ i) 46 for(int j = 1;j <= m; ++ j){ 47 read(a[i][j]); 48 } 49 for(int i = 1;i <= n; ++ i) read(b[i]); 50 } 51 52 void work(){ 53 int last = 0,cur = -2e9,now = 0; 54 for(int i = 1;i <= m; ++ i){ 55 cur = -2e9; 56 for(int j = 1;j <= n; ++ j){ 57 int pre = j - 1; 58 if(!pre) pre = n; 59 dp[now][1][j] = last - b[pre] + a[pre][i]; 60 cur = Max(cur,dp[now][1][j]); 61 } 62 for(int k = 2; k <= min(i,p); ++ k){ 63 int k1 = k - 1; 64 for(int j = 1;j <= n; ++ j){ 65 int pre = j - 1; 66 if(!pre) pre = n; 67 dp[now][k][j] = dp[now ^ 1][k1][pre] + a[pre][i];//a[pre][i] 68 cur = Max(cur,dp[now][k][j]); 69 } 70 } 71 last = cur;now ^= 1; 72 } 73 put(cur); 74 } 75 76 int main(){ 77 // file(); 78 readdata(); 79 work(); 80 return 0; 81 }
（2）单调队列优化
推荐一篇题解：题解 P1070 【道路游戏】
原文：https://www.cnblogs.com/Mandy-H-Y/p/11416351.html
