P1070 道路游戏

[永遠の記憶 ~ Precious Memories]施工D4

转载自luogu 2020.3.6

Noip2009 T4

题目传送门

题目比较长，但是说的事情比较简单，就是求一个收点方案，并使收率最大
不难看出，这是一道动规，那我们先考虑一下题目中的不定量

1. 从哪个工厂开始走(n种选择，1e3)

2. 可以收点的总时间(m个单位内，1e3)

然后去考虑我们要去干的事情

3. 走路收点(p种选择, 1e3）

综合123，我们总共的时间复杂度是O(n^3)
其中n = 1e3，应该是可以过的
我们先写循环，然后再推状态转移方程式
代码中的主体应该是长这样:

for (int i = 1; i <= m; ++i) { 
	for (int j = 1; j <= n; ++j) { 
		for (int k = 0; (i + k <= m) && (k < p); ++k) { 
			//...
		}
	}
}

最外层是m次，表示击破时间

第二层有n次，枚举出生点

最里面一层是一个k值，表示自机存活时间，从零开始是因为与i+k<=m的判断时间对应，因为购买自机不需要花费时间

接下来，我们可以开始愉快地推方程了
我最开始写的dp数组是一个三维的，结果爆内存了。。。
然后我就想，既然我不能写三维的，
我两维的也不知道怎么表示
那就干脆头铁写个一维的吧
其中dp[i]表示时间i时的最大收点数
然后我们把题目中的购买自机的钱表示为rob数组
点数及其变化表示为w数组

那么我们很容易可以得到下式:

dp[i + k] = max(dp[i + k], dp[i – 1] – rob[j] + ∑w[j + k][i + k](k < p));

其中后面的一个∑就类似求一个前缀和的东西，因为你收点时也算以前收过的嘛(不知道这样能不能听懂。。。
最后，根据上式，再配合一些处理步数的操作，我们就可以写出最终的代码了!
代码如下:

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

const int maxn = 1e3 + 5;
const int maxm = 1e3 + 5;
int n, m, p;
int w[maxn][maxm];
int rob[maxn];
int dp[maxn];

int main() {
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= m; ++i) dp[i] = -1e6;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &w[i][j]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &rob[i]);
	}
	for (int i = 1; i <= m; ++i) { // 击破时间  
		for (int j = 1; j <= n; ++j) { // 起步  
			int temp = dp[i - 1] - rob[j]; // 付完钱剩下的钱  
			for (int k = 0; (i + k <= m) && (k < p); ++k) { // 收点  
				int idx = j + k;
				if (idx > n) idx %= n; 
				// 这里idx > n也不是很清楚是怎么来的，反正试了一下，就这个可以过  
				temp += w[idx][i + k]; // 累计，相当于一个前缀和之类的东西  
				dp[i + k] = max(temp, dp[i + k]);
			}
		}
	}
	printf("%d\n", dp[m]);
	return 0;
}

最后呢，其实这道题作为一道dp，其实也不算太难，个人感觉也就绿题水平吧 (~~pj省二蒟蒻瞎扯~~
如果当年在考场上的话，估计就直接放弃不做了吧
因为这道题细节有点多
这种题目还是比较锻炼思维的，~~不像模拟那么无脑~~
以后有空多做点dp吧！

[永遠の記憶 ~ Precious Memories]施工D4