【NOIP2009PJ】【DP】道路游戏

$Link$

$luogu\ P1070$

$Description$

$Sample$ $Input$

2 3 2 
1 2 3 
2 3 4 
1 2

$Sample$ $Output$

5

$Hint$

$Train$ $of$ $Thought$

dp
设$f_i$表示到第$i$个单位时间时所积累的最大金币数
然后枚举机器人投放位置以及设定的移动距离

$Code$

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n, m, p;
int f[1001], num[1001][1001], num1[1001]; 

int work(int x)
{
	if (x < 1) return n;
	return x;
}

int main()
{
	memset(f, -0x7f, sizeof(f));
	f[0] = 0;
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		scanf("%d", &num[i][j]);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &num1[i]);
	for (int i = 1; i <= m; ++i)
	for (int j = 1; j <= n; ++j)
	{
		int last = work(j - 1);//枚举上一个位置
		int walkget = num[last][i];//这次移动赚的钱
		for (int k = 1; k <= p; ++k)
		{
			if (i - k >= 0) 
			{
				f[i] = max(f[i], f[i - k] + walkget - num1[last]);//判断当前大还是枚举的前面的大
				last = work(last - 1);//更新上次移动的点
				walkget += num[last][i - k];//更新攒的钱
			}	
			else break;
		}
	}
	printf("%d", f[m]);
	return 0;
} 

本文地址：https://blog.****.net/LTH060226/article/details/107898927