链接：P1541 [NOIP2010 提高组] 乌龟棋。

题意

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

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

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

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同。现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，求最多能得到多少分。

数据范围

$1\le n\le350$ ， $M\le120$ ， $m_i\le40$ ， $0\le a_i\le100$ 。

点击查看题解

题解

使用 DP 求解。无后效性分析：只能前进，无法后退，也就没有环路。

首先我们可以设 $f(i,j,k,l,n)$ 表示用掉操作的状态有 $i$ ， $j$ ， $k$ ， $l$ ，到达 $n$ 点后的所能取得的最大分数（前 $4$ 维分别表示用掉的 $4$ 种操作的数目，后一维表示已经到达的点）。

之后，发现后一维可以用前四维求得，且五维数组爆空间，于是将最后一维降掉。

于是设 $f(i,j,k,l)$ 表示用掉操作的状态有 $i$ ， $j$ ， $k$ ， $l$ 后的所能取得的最大分数。可推得状态转移方程：

f(\texttt{now})=\max\{f(\texttt{pre})+a_\texttt{now}\}

其中， $\texttt{now}$ 指当前状态， $\texttt{pre}$ 指比当前状态少一个操作的状态。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=400,M=40+5;
	int f[M][M][M][M],n,m,a[N],b[N];
	void yzmain()
	{
		int tmp;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",a+i);
		for(int i=1;i<=m;i++)
			scanf("%d",&tmp),
			b[tmp]++;
		for(int i=0;i<=b[1];i++)
		 for(int j=0;j<=b[2];j++)
		  for(int k=0;k<=b[3];k++)
		   for(int l=0;l<=b[4];l++)
		   {
			tmp=0;
			if(i>=1) tmp=max(tmp,f[i-1][j][k][l]);
			if(j>=1) tmp=max(tmp,f[i][j-1][k][l]);
			if(k>=1) tmp=max(tmp,f[i][j][k-1][l]);
			if(l>=1) tmp=max(tmp,f[i][j][k][l-1]);
			f[i][j][k][l]=tmp+a[1+i*1+j*2+k*3+l*4];
		   }
		printf("%d\n",f[b[1]][b[2]][b[3]][b[4]]);
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/3f632052a0ae/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划

最后更新：2023-08-21, 23:18:20

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158