P1541 [NOIP2010 提高组] 乌龟棋

题目

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

对于 $100\%$ 的数据有 $1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。

题解

设f[i][j][k][l]为选择了i张前进1格，j张2，k张3，l张4所能获得的最大利润

转移即可

问题

1.line55，要加1

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 355;
int a[N], n, m;
int num[5];
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}
int f[42][42][42][42];


int main()
{
	memset(f, -0x3f, sizeof f);
	n = read(), m = read();
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
	}

	int t;

	for(int i = 1;i <= m;i++)
	{
		t = read();
		num[t]++;
	}
	f[0][0][0][0] = a[1];
	int ans = -0x7f7f7f7f;
	for(int i = 0;i <= num[1];i++)
	{
		for(int j = 0;j <= num[2];j++)
		{
			for(int k = 0;k <= num[3];k++)
			{
				for(int l = 0;l <= num[4];l++)
				{
					if(i == j && j == k && k == l && i == 0) continue;
					int x = 1 + i + 2 * j + 3 * k + 4 * l;
					if(x > n) continue;
					if(i - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l] + a[x]);
					if(j - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l] + a[x]);
					if(k - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l] + a[x]);
					if(l - 1 >= 0)
						f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1] + a[x]);
					ans = max(ans, f[i][j][k][l]);
				}
			}
		}
	}

	printf("%d", ans);

	return 0;
}