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;
}