博客

b站视频

https://www.bilibili.com/video/BV1iT4y1U7tV/

• 时间复杂度
  
  
  
  O

  (

  n

  3

  O(n^3
  
  
  
  
  
  
  O
  
  
  (
  
  
  
  n
  
  
  
  
  
  
  
  
  
  
  3
  
  
  
  
  
  
  
  
  
  
  
  
  )

#include <bits/stdc++.h>
using namespace std;

const int N = 1009;
int n, m, p;
int gold[N][N];		//gold[i][j]:i号条路j时刻出现的金币
int cost[N];		//cost[i]:i号工厂购买机器人的费用 
int f[N];			//f[j]:j时刻得到的最多金币 

int main() {
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> gold[i][j];
		}
	}
	for (int i = 1; i <= n; i ++) cin >> cost[i];
	
	for (int j = 1; j <= m; j ++) {	
		for (int i = 1; i <= n; i ++) {
			//j-1时刻在i-1号马路机器人停止行走 
			//j时刻在i号马路购买一个机器人，行走k次
			int tmp = f[j - 1] - cost[i]; 
			for (int k = 1; k <= min(m - j + 1, p); k ++) {
				int road = (i - 1) + k;
				if (road > n) road -= n;
				int time = (j - 1) + k;
				
				tmp += gold[road][time];
				f[time] = max(f[time], tmp);
			}
		}
	}
	cout << f[m];
	
	return 0;
}