【每日一题】乌龟棋
乌龟棋
https://ac.nowcoder.com/acm/problem/16590
题目
题目描述：
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例）。
每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。
游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。
玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
输入描述：
第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数，a1, a2, ……, aN，其中ai表示棋盘第i个格子上的分数。
第3行M个整数，b1,b2, ……, bM，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片，即 N−1=∑1Mbi
输出描述：
输出只有1行，1个整数，表示小明最多能得到的分数。
第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数，a1, a2, ……, aN，其中ai表示棋盘第i个格子上的分数。
第3行M个整数，b1,b2, ……, bM，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片，即 N−1=∑1Mbi
输出描述：
输出只有1行，1个整数，表示小明最多能得到的分数。
解析
1）知识点
- 这道题其实就是简单的动态规划，只是我在看邓老师的题解之前，没想到dp数组还能这样写。
2）看题目
- 题目不难理解，有N个格子，每个格子有不同的分数，请问你用不同的走法（一二三四步，每个的步数确定了），可以得到的最大分数。
3）算法分析
- 首先既然已经知道是dp，那么还是这句话：动态规划最重要的就是递推和dp数组的构建。
- 首先就是dp数组的含义：
- 我一开始是想，先来一维表示位置，再来一维表示当前位置的分数。但是我还是太天真，这样子怎么确定每一种步数用了多少次呢QAQ
- 然后看了邓老师的题解以后豁然开朗，我还是忘记了我当初一直念叨的东西。
- 我们这道题里面重要的东西就是我们所在的位置，还有每一种步数到底用过了多少次。
- 然后这里的数据大小疯狂的给了我们提示，每一种步数最多也就40个，也就是说，来个四维五维都不是大问题（况且，就只有四种步数）。
- 接下来呢，我们就可以用步数，做一个四维数组，表示每一种步数用过了多少次。这个时候，我们不需要第五维（位置）了，因为可以算出来呀，每一种步数乘上次数不就是吗。
- 既然dp数组已经出来了，递推就好办了：
- 这里递推特别简单，和背包一样，就是把四种步数撤销重算，看会不会更大。
- 这里注意在四种步数为0的时候要特判一下，因为这个时候无法撤销上一次的步数。
4）算法操作
- 所以我们首先把我们的dp数组亮出来吧：
int dp[MAXcard][MAXcard][MAXcard][MAXcard];//dp[已用a][已用b][已用c][已用d] = 最大分数
- 在这里呢，我们用a，b，c，d四个数据，来表示我们每种卡的数量，在最开始统计一下就好了。
- 然后就是我们的递推过程了，这里必不可少的就是我们的四重循环递推啦，一起看看：
for (int i = 0; i <= a; i++) for (int j = 0; j <= b; j++) for (int k = 0; k <= c; k++) for (int l = 0; l <= d; l++) { int step = i * 1 + j * 2 + k * 3 + l * 4;//步数可以用使用方法推理出来 int& tmp = dp[i][j][k][l];//tmp表示当前的使用方法的最大情况 tmp = score[step];//初始化为当前格子的分数（这个分数一定有，所以先初始化） if (i) tmp = max(tmp, dp[i - 1][j][k][l] + score[step]); if (j) tmp = max(tmp, dp[i][j - 1][k][l] + score[step]); if (k) tmp = max(tmp, dp[i][j][k - 1][l] + score[step]); if (l) tmp = max(tmp, dp[i][j][k][l - 1] + score[step]); }
5）打代码
- 打代码咯
- 首先我们先要输入数据，这里注意保存用的数据是什么就行了。
- 然后呢就直接递推就好啦，代码不难思路难，好好看看吧。
- 看我代码咯~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//预处理
const int MAXN = 357;
const int MAXcard = 47;
int N, M;//N个格子和M张卡片
int a, b, c, d;//表示四种卡片的个数
int score[MAXN];//每个格子上面的分数
int dp[MAXcard][MAXcard][MAXcard][MAXcard];//dp[已用a][已用b][已用c][已用d] = 最大分数
//全局变量
int main() {
IOS;
cin >> N >> M;
a = b = c = d = 0;
for (int i = 0; i < N; i++) cin >> score[i];
for (int i = 0; i < M; i++) {
int x; cin >> x;
if (x == 1) a++;
else if (x == 2) b++;
else if (x == 3) c++;
else if (x == 4) d++;
}
//输入
for (int i = 0; i <= a; i++)
for (int j = 0; j <= b; j++)
for (int k = 0; k <= c; k++)
for (int l = 0; l <= d; l++) {
int step = i * 1 + j * 2 + k * 3 + l * 4;//步数可以用使用方法推理出来
int& tmp = dp[i][j][k][l];//tmp表示当前的使用方法的最大情况
tmp = score[step];//初始化为当前格子的分数（这个分数一定有，所以先初始化）
if (i) tmp = max(tmp, dp[i - 1][j][k][l] + score[step]);
if (j) tmp = max(tmp, dp[i][j - 1][k][l] + score[step]);
if (k) tmp = max(tmp, dp[i][j][k - 1][l] + score[step]);
if (l) tmp = max(tmp, dp[i][j][k][l - 1] + score[step]);
}
//操作
cout << dp[a][b][c][d] << endl;
//输出
return 0;
}每日一题 文章被收录于专栏
憨憨的专栏
