【洛谷 P1070】道路游戏（DP）

这题还是很好想的，看到\(90%\)的数据点时，我就知道要用\(n^3\)的算法（最后10分就算了吧）

然后，数据水，直接暴力\(n^3\)卡过了。

显然是道DP。

设\(f[i]\)表示第\(i\)秒获取到的最多的金币。

三重循环更新状态。

第一重枚举机器人出发时间，

第二重枚举机器人出发地点，

第三重枚举机器人停止的时间。

很容易理解，看代码一下就懂了。

#include <cstdio>

#include <cmath>

#include <algorithm>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

#define INF 2147483647

using namespace std;

const int MAXN = 1010;

int tmp, n, m, p;

int coin[MAXN][MAXN], f[MAXN], cost[MAXN];

int getnext(int x){

	tmp = (x + 1) % n;

	if(!tmp) tmp = n;

	return tmp;

}

int Min = INF;

int main(){

	//Open("game");

	scanf("%d%d%d", &n, &m, &p);

	for(int i = 1; i <= n; ++i)

		for(int j = 1; j <= m; ++j)

			scanf("%d", &coin[i][j]);

	for(int i = 1; i <= n; ++i)

		scanf("%d", &cost[i]), Min = min(Min, cost[i]);

	for(int i = 1; i <= m; ++i)

        f[i] = -Min;

	for(int i = 1; i <= m; ++i)

		for(int j = 1; j <= n; ++j){

			int sum = 0, now = j;

			for(int k = i; k <= min(m, i + p - 1); ++k)

				f[k] = max(f[k], f[i - 1] + (sum += coin[now][k]) - cost[j]), now = getnext(now);

		}

	printf("%d\n", f[m]);

	return 0;

}

巴特西

【洛谷 P1070】道路游戏（DP）

最新文章

热门文章

巴特西

【洛谷 P1070】道路游戏 （DP）

最新文章

热门文章

【洛谷 P1070】道路游戏（DP）