题解【luogu P1541 NOIp提高组2010 乌龟棋】

题解

题意：

有一些格子，每个格子有一定分数。

给你四种卡片，每次可以使用卡片来前进1或2或3或4个格子并拾取格子上的分数

每张卡片有数量限制。求最大分数。

分析

设\(dp[i]\)为第前\(i\)个格子所能得到的最大分数

显然有一个简单的转移方程

\(dp[i] = \max(dp[i-1] ,dp[i-2],dp[i-3],dp[i-4])\)

等等，，卡片有数量限制！所以上面的方程就不行了

换一个思路，既然它有限制，就以毒攻毒设\(dp[i][j][k][l]\)为用了\(i\)张卡片1，\(j\) 张卡片2 \({...}\) \(l\) 张卡片4

设\(Go\)为现在在第几个格子。则\(Go=1+i*1+j*2+k*3+l*4\) 则转移方程为

\[dp[i][j][k][l] = \max(
dp[i][j][k][l],
dp[i-1][j][k][l]+mark[Go],
dp[i][j-1][k][l]+mark[Go],
{...},dp[i][j][k][l-1]+mark[Go])\]

实现简单

注意

\(dp[i-1][j][k][l]\)中的\(i-1\)在\(i=0\)是会溢出，需要特判

代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

using namespace std;

const int MAXN = 400;

const int MAXM = 150;

int n, m;

int mark[MAXN], card[MAXM];

int dp[45][45][45][45];

int card_sum[5];

int main()

{

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i++) scanf("%d", &mark[i]);

	for(int i = 1; i <= m; i++) scanf("%d", &card[i]), card_sum[card[i]]++;

	dp[0][0][0][0] = mark[1];

	for(int i = 0; i <= card_sum[1]; i++)

		for(int j = 0; j <= card_sum[2]; j++)

			for(int k = 0; k <= card_sum[3]; k++)

				for(int l = 0; l <= card_sum[4]; l++)

				{

					int Go = 1 + i + j * 2 + k * 3 + l * 4;

					if(i) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + mark[Go]);

					if(j) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + mark[Go]);

					if(k) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + mark[Go]);

					if(l) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + mark[Go]);

				}

    printf("%d\n", dp[card_sum[1]][card_sum[2]][card_sum[3]][card_sum[4]]);

	return 0;

}

巴特西

题解【luogu P1541 NOIp提高组2010 乌龟棋】

最新文章

热门文章

巴特西

题解 【luogu P1541 NOIp提高组2010 乌龟棋】

最新文章

热门文章

题解【luogu P1541 NOIp提高组2010 乌龟棋】