原题链接：https://www.luogu.com.cn/problem/P1070
题意解读：1~n个环形机器人工厂，相邻工厂之间的道路是1~n，每个时刻可以从任意工厂购买机器人，走不超过p时间，不同工厂购买机器人花费不同的金币，不同时刻走到不同道路也能得到不同的金币，问一共m时间，最多可以得到多少金币（需减去购买机器人的花费）。
解题思路：
1、状态表示
有n个机器人工厂、n条马路、m个时间，每次机器人最多走p时间，
设a[i][j]表示走第i号马路，第j时刻产生的金币数，
设b[i]表示从第i号机器人工厂购买机器人所消耗的金币数，
设dp[i]表示前i时间能得到的最多金币数。
2、样例模拟
2 3 2
1 2 3
2 3 4
1 2一共有2个机器人工厂，总共走3步，每次购买机器人最多走2步
道路在不同时刻产生的金币数：
| 时刻：1 | 时刻：2 | 时刻：3 | |
| 道路：1 | 1 | 2 | 3 |
| 道路：2 | 2 | 3 | 4 |
每个机器人工厂购买机器人的花费：
| 工厂号 | 购买机器人金币数 |
| 工厂：1 | 1 |
| 工厂：2 | 2 |
第1时刻：
从工厂1购买机器人：
走1步：dp[1] = -1 + 1 = 0，说明：-从工厂1购买机器人+第1时刻走道路1
走2步：dp[2] = -1 + 1 + 3 = 3，说明：-从工厂1购买机器人+第1时刻走道路1+第2时刻走道路2
从工厂2购买机器人：
走1步：dp[1] = -2 + 2 = 0，说明：-从工厂2购买机器人+第1时刻走道路2
走2步：dp[2] = -2 + 2 + 2 = 2，说明：-从工厂2购买机器人+第1时刻走道路2+第2时刻走道路1
此时，dp[1]的最大值为0，dp[2]的最大值为3，所以dp[1] = 0，dp[2] = 3
第2时刻：
从工厂1购买机器人：
走1步：dp[2] = f[1] - 1 + 1 = 0，说明：前1个时间获得的最大金币数-从工厂1购买机器人+第2时刻走道路1
走2步：dp[3] = f[1] - 1 + 1 + 4，说明：前1个时间获得的最大金币数-从工厂1购买机器人+第2时刻走道路1+第3时刻走道路2
从工厂2购买机器人：
走1步：dp[2] = f[1] - 2 + 3 = 1， 说明：前1个时间获得的最大金币数-从工厂2购买机器人+第2时刻走道路2
走2步：dp[3] = f[1] - 2 + 3 + 3 = 4，说明：前1个时间获得的最大金币数-从工厂2购买机器人+第2时刻走道路2+第3时刻走道路1
此时，dp[2]的最大值为3，所以dp[2] = 3
第3时刻：（一共m=3，到第3时刻就只能走1步了）
从工厂1购买机器人：
走1步：dp[3] = dp[2] - 1 + 3 = 5，说明：前2个时间获得的最大金币数-从工厂1购买机器人+第3时刻走道路1
从工厂2购买机器人：
走1步：dp[3] = dp[2] - 2 + 4 = 5，说明：前2个时间获得的最大金币数-从工厂2购买机器人+第3时刻走道路2
此时，dp[3]的最大值为5，所以最终答案就是dp[3] = 5。
3、状态转移
根据以上分析，可以通过三重循环来枚举实现递推
for i：1 ~ m的时刻
for j：1 ~ n的工厂
sum = dp[i-1] - 从工厂j购买机器人的花费
for k：1 ~ p的步数（注意：走k步后时间不能超过m）
走到的工厂位置 = j + k - 1
if(走到的工厂位置 % n) //处理环形
走到的工厂位置 %= 走到的工厂位置
当前时刻 = i + k - 1
sum += a[走到的工厂位置][当前时刻]
dp[当前时刻] = max(dp[当前时刻]，sum)
4、初始值
初始化为极大值
for(int i = 1; i <= n; i++) dp[i] = -0x3f3f3f3f;5、结果
根据定义为dp[m]
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 1005;
int n, m, p;
int a[N][M]; //a[i][j]表示第i号马路，第j时刻的金币数
int b[N]; //b[i]表示第i号机器人工厂购买机器人的金币数
int dp[N]; //dp[i]表示前i时间能得到的最多金币数
int main()
{
cin >> n >> m >> p;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
cin >> b[i];
for(int i = 1; i <= n; i++) dp[i] = -0x3f3f3f3f;
for(int i = 1; i <= m; i++) //枚举时刻
{
for(int j = 1; j <= n; j++) //枚举工厂
{
int sum = dp[i-1] - b[j]; //sum初始是前i-1时间的最大收益减去在j工厂购买机器人的消耗
for(int k = 1; k <= p && i + k - 1 <= m; k++)
{
int pos = j + k - 1; //走到哪个工厂
if(pos % n) pos %= n;
int time = i + k - 1; //当前的时刻
sum += a[pos][time]; //sum加上走到pos马路time时刻获得的金币
dp[time] = max(dp[time], sum);
}
}
}
cout << dp[m];
return 0;
}标签：洛谷题,机器人,NOIP2009,工厂,金币,购买,时刻,dp,P1070 From： https://www.cnblogs.com/jcwy/p/18191936