刷题记录:牛客NC16590乌龟棋

传送门:牛客

题目描述:

乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例），每
种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前
进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬
行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到
过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？ 
输入:
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1
输出:
73
1
2
3
4
5
6
7
8
9
10
11
12
13

对于这道题,对于dp方程感觉不是很难的一件事情.因为显然的,只有一个数轴的移动,这就意味着我们的当前位置的状态显然是由数轴之前的位置转移而来.但是我们会发现一个问题.我们的卡片每次都是只能用有限次数的,所以我们还需要想办法存储我们当前状态的卡片的使用情况.

此时我们再重新看一下题目,我们会发现其实我们的卡片用完之后是恰恰到达我们的终点的,因此我们最终的状态就是我们的卡牌用完的时候.因此我们其实直接记录我们的每一个卡片的使用情况,来由此推出我们最终的答案即可

我们使用$dp[a][b][c][d]来记录我们的4种卡牌分别使用a,b,c,d张时我们的最大得分$
那么显然的我们的可以由之前的$dp[a-1][b][c][d],dp[a][b-1][c][d],dp[a][b][c-1][d],dp[a][b][c][d-1]$转移而来.搞清楚以上几点之后我们的代码也就不难写出了

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;
int num[maxn];
int a,b,c,d;
int dp[60][60][60][60];
int main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) num[i]=read();
	int bi;
	for(int i=1;i<=m;i++) {
		bi=read();
		if(bi==1) a++;
		else if(bi==2) b++;
		else if(bi==3) c++;
		else d++;
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[0][0][0][0]=num[1];
	for(int i=0;i<=a;i++) {
		for(int i2=0;i2<=b;i2++) {
			for(int i3=0;i3<=c;i3++) {
				for(int i4=0;i4<=d;i4++) {
					int pos=1+i+i2*2+i3*3+i4*4;
					if(i>0) dp[i][i2][i3][i4]=max(dp[i][i2][i3][i4],dp[i-1][i2][i3][i4]+num[pos]);
					if(i2>0) dp[i][i2][i3][i4]=max(dp[i][i2][i3][i4],dp[i][i2-1][i3][i4]+num[pos]);
					if(i3>0) dp[i][i2][i3][i4]=max(dp[i][i2][i3][i4],dp[i][i2][i3-1][i4]+num[pos]);
					if(i4>0) dp[i][i2][i3][i4]=max(dp[i][i2][i3][i4],dp[i][i2][i3][i4-1]+num[pos]);
				}
			}
		}
	}
	cout<<dp[a][b][c][d]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59