题解：P1541 [NOIP2010 提高组] 乌龟棋

题目大意

给

n

个格子，每个格子上都有一定的分数。再给

m

张数值为

1

到

4

的卡片，卡片上的数值代表前进的步数，每张卡片只能用一次。每到达一个格子就可以拿走该分数，问所有卡片用光时能够获得的最大分数。

解题思路

一眼动态规划，上动态规划六步分析法。

一、定义问题状态

题目中共计四种卡片，每种卡片的数量与得分之间有联系，状态非常好设计。

f(a,b,c,d)

表示第

1

种卡片使用

a

张，第

2

种卡片使用

b

张，第

3

种卡片使用

c

张，第

4

种卡片使用

d

张时的最大分值。

二、分解子问题

分解子问题的目的是将问题拆分为相似的规模更小的问题，从而得到，子问题与原问题之间的状态转移方程。分解子问题时需要考虑，决策与约束条件。

f(a,b,c,d)=\max\begin{cases}f(a-1,b,c,d) + sc[step] & a\ge 1\\ f(a,b-1,c,d) + sc[step] & b\ge 1\\ f(a,b,c-1,d) + sc[step] & c\ge 1\\f(a,b,c,d-1) + sc[step] & d\ge 1\end{cases}

其中

step=a+2\times b+3\times c+4\times d+1

三、初始化边界状态

边界状态即为不需要计算就能直接分析出的状态。这里是一张卡片都没有用时得分为在第

1

格处的分数。

f(0,0,0,0)=sc[1]

四、计算顺序

从小到大依次枚举卡片

1

至

4

的张数。

五、最终答案

ans=f(cnt1,cnt2,cnt3,cnt4)

其中

cnt1

至

cnt4

表示第

1

至第

4

张卡片的总数量。

六、效率分析

时间复杂度和空间复杂度度都为

O(n^4)

这里

n

代表每种卡片的最大数量为

40

没有超时和超空间。

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;

const int maxn = 10005;
int n, m, a[maxn], b, cnt[5], f[52][52][52][52];

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++){
		cin >> b;
		cnt[b]++;
	}
	f[0][0][0][0] = a[1];
	for(int i = 0; i <= cnt[1]; i++)
		for(int j = 0; j <= cnt[2]; j++)
			for(int k = 0; k <= cnt[3]; k++)
				for(int l = 0; l <= cnt[4]; l++){
					int step = i+2*j+3*k+4*l+1;
					if(i) f[i][j][k][l] = max(f[i][j][k][l], f[i-1][j][k][l] + a[step]);
					if(j) f[i][j][k][l] = max(f[i][j][k][l], f[i][j-1][k][l] + a[step]);
					if(k) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k-1][l] + a[step]);
					if(l) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l-1] + a[step]);
				}
	cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];
	return 0;
}

题解：P1541 [NOIP2010 提高组] 乌龟棋

文章操作

题目大意

解题思路

一、定义问题状态

二、分解子问题

三、初始化边界状态

四、计算顺序

五、最终答案

六、效率分析

代码实现

相关推荐

评论

题解：P1541 [NOIP2010 提高组] 乌龟棋