【NOIP2009PJ】【DP】道路游戏

L i n k Link Link

l u o g u   P 1070 luogu\ P1070 luogu P1070

D e s c r i p t i o n Description Description

S a m p l e Sample Sample I n p u t Input Input

2 3 2 
1 2 3 
2 3 4 
1 2

S a m p l e Sample Sample O u t p u t Output Output

5

H i n t Hint Hint

T r a i n Train Train o f of of T h o u g h t Thought Thought

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

C o d e Code 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.csdn.net/LTH060226/article/details/107898927