题目大意

一行格子，每个格子里有数字。一些卡片，卡片上有1、2、3、4这几种数字。一开始你在格子1，随后每次选一个卡片，你可以前进卡片上的数字个格子，得到格子上的分数，然后讲该卡片丢弃。求取卡片的顺序，使得得到的分数之和最大。

题解

定义\(A\)数组为格子上的各个数字，\(f(p,a,b,c,d)\)为从位置1走到位置\(p\)，已经用了\(a\)个数字1卡片，\(b\)个数字2卡片，\(c\)个数字3卡片，\(d\)个数字4卡片时，得到的分数的最大值。则有递归式：

\[f(p,a,b,c,d)=A_p +\max(f(p-1,a-1,b,c,d),f(p-2,a,b-1,c,d),f(p-3,a,b,c-1,d),f(p-4,a,b,c,d-1))
\]

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define LOOP(i, n) for(int i = 1; i <= n; i++)

const int MAX_TABLE = 400, MAX_SORT_CARD_CNT = 15;

int F[MAX_TABLE][MAX_SORT_CARD_CNT][MAX_SORT_CARD_CNT][MAX_SORT_CARD_CNT][MAX_SORT_CARD_CNT];

int Table[MAX_TABLE];

int SortCardCnt[5];

int TotTable, TotCard;

int DP(int p, int a, int b, int c, int d)

{

	if (p < 0 || a < 0 || b < 0 || c < 0 || d < 0)

		return -1;

	if (F[p][a][b][c][d] > 0)

		return F[p][a][b][c][d];

	int op1 = DP(p - 1, a - 1, b, c, d);

	int op2 = DP(p - 2, a, b - 1, c, d);

	int op3 = DP(p - 3, a, b, c - 1, d);

	int op4 = DP(p - 4, a, b, c, d - 1);

	return F[p][a][b][c][d] = max(op1, max(op2, max(op3, op4))) + Table[p];

}

int main()

{

	int cardSort;

	scanf("%d%d", &TotTable, &TotCard);

	LOOP(i, TotTable)

		scanf("%d", Table + i);

	LOOP(i, TotCard)

	{

		scanf("%d", &cardSort);

		SortCardCnt[cardSort]++;

	}

	memset(F, -1, sizeof(F));

	F[1][0][0][0][0] = Table[1];

	printf("%d\n", DP(TotTable, SortCardCnt[1], SortCardCnt[2], SortCardCnt[3], SortCardCnt[4]));

	return 0;

}

巴特西

luogu1541 乌龟棋动态规划

题目大意

题解

最新文章

热门文章

巴特西

luogu1541 乌龟棋 动态规划

题目大意

题解

最新文章

热门文章

luogu1541 乌龟棋动态规划