洛谷P1541题解

此题解使用DP

由于本题保证每种卡片的张数不会超过$40$ 且 保证到达终点时刚好用光$M$张爬行卡片，所以将dp数组设置为四维（第一维表示第一张卡片使用的次数，第二维表示第二张卡片使用的次数$\cdots$）

时间复杂度：$O(ca[1]*ca[2]*ca[3]*ca[4])$

$(ca[i]:能前进i步的卡牌的数量)$

状态转移方程

int np=1+i+j*2+k*3+k1*4;//存储当前点(记得乌龟棋是从1开始的)
if(i)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i-1][j][k][k1]+ti[np]);
if(j)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j-1][k][k1]+ti[np]);
if(k)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j][k-1][k1]+ti[np]);
if(k1)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j][k][k1-1]+ti[np]);

AC代码

#include <iostream>
#include <cstring>
#include <cmath>
#define NM 351
#define TM 41
using namespace std;
int n,m,dp[TM][TM][TM][TM],ti[NM],ca[5];
//dp:四维dp数组,ti:存储乌龟棋分数,ca:存储每种牌的数量
int main()
{
	memset(dp,0,sizeof(dp));
	memset(ca,0,sizeof(ca));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&ti[i]);
	for(int i=1;i<=m;++i)
	{
		int tmp;
		scanf("%d",&tmp);
		ca[tmp]++;
	}
	//dp开始
	dp[0][0][0][0]=ti[1];
	for(int i=0;i<=ca[1];i++)
	{
		for(int j=0;j<=ca[2];j++)
		{
			for(int k=0;k<=ca[3];k++)
			{
				for(int k1=0;k1<=ca[4];k1++)
				{
					int np=1+i+j*2+k*3+k1*4;//存储当前点(记得乌龟棋是从1开始的)
					
					//状态转移方程
					if(i)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i-1][j][k][k1]+ti[np]);
					if(j)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j-1][k][k1]+ti[np]);
					if(k)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j][k-1][k1]+ti[np]);
					if(k1)dp[i][j][k][k1]=max(dp[i][j][k][k1],dp[i][j][k][k1-1]+ti[np]);
				}
			}
		}
	}
	printf("%d",dp[ca[1]][ca[2]][ca[3]][ca[4]]);
	return 0;
}