【题目来源】
洛谷：P1541 [NOIP 2010 提高组] 乌龟棋 - 洛谷
【题目描述】
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行 \(N\) 个格子，每个格子上一个分数（非负整数）。棋盘第 \(1\) 格是唯一的起点，第 \(N\) 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 \(M\) 张爬行卡片，分成 \(4\) 种不同的类型（\(M\) 张卡片中不一定包含所有 \(4\) 种类型的卡片，见样例），每种类型的卡片上分别标有 \(1,2,3,4\) 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
【输入】
每行中两个数之间用一个空格隔开。
第 \(1\) 行 \(2\) 个正整数 \(N,M\)，分别表示棋盘格子数和爬行卡片数。
第 \(2\) 行 \(N\) 个非负整数，\(a_1,a_2,\dots,a_N\)，其中 \(a_i\) 表示棋盘第 \(i\) 个格子上的分数。
第 \(3\) 行 \(M\) 个整数，\(b_1,b_2,\dots,b_M\)，表示 \(M\) 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 \(M\) 张爬行卡片。
【输出】
一个整数，表示小明最多能得到的分数。
【输入样例】
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
【输出样例】
73
【解题思路】
【算法标签】
《洛谷 P1541 乌龟棋》 #动态规划,dp# #递归# #枚举# #NOIP提高组# #2010#
【代码详解】
// 使用记忆化DFS
#include <bits/stdc++.h>
using namespace std;int x, n, m; // x: 临时变量, n: 格子数, m: 卡片数
int a[355]; // 存储每个格子的分数
int b[5]; // 记录每种步长的卡片数量（b[1]-b[4]）
int dp[45][45][45][45]; // 记忆化数组，记录状态/*** 记忆化搜索函数* @param pos 当前位置* @return 从当前位置出发能获得的最大分数*/
int dfs(int pos)
{int s = 0; // 临时存储最大值// 终止条件：到达终点if (pos == n) return a[n];// 记忆化：如果状态已计算过，直接返回结果if (dp[b[1]][b[2]][b[3]][b[4]]) return dp[b[1]][b[2]][b[3]][b[4]];// 尝试使用每种步长的卡片for (int i = 1; i <= 4; i++){// 如果没有该步长的卡片，跳过if (b[i] == 0) continue;// 使用一张卡片b[i]--;// 递归计算下一步的最大值s = max(s, dfs(pos + i));// 恢复卡片数量（回溯）b[i]++;}// 记忆化存储结果：当前最大分数加上当前位置的分数return dp[b[1]][b[2]][b[3]][b[4]] = s + a[pos];
}int main()
{// 输入格子数和卡片数cin >> n >> m;// 输入每个格子的分数for (int i = 1; i <= n; i++){cin >> a[i];}// 输入每张卡片的步长并统计数量for (int i = 1; i <= m; i++){cin >> x;b[x]++;}// 从起点开始搜索并输出结果cout << dfs(1);return 0;
}
// 动态规划
#include <bits/stdc++.h>
using namespace std;int a[355]; // 存储每个格子的分数
int dp[45][45][45][45]; // 四维DP数组，记录不同卡片使用组合下的最大得分
int b[5]; // 记录每种步长卡片的数量（b[1]-b[4]）
int n, m; // n: 格子总数，m: 卡片总数int main()
{// 输入格子数和卡片数cin >> n >> m;// 输入每个格子的分数for (int i = 1; i <= n; i++){cin >> a[i];}// 输入每张卡片的步长并统计数量for (int i = 1; i <= m; i++){int x;cin >> x;b[x]++;}// 初始化DP数组：不使用任何卡片时的得分为起点格子的分数dp[0][0][0][0] = a[1];// 四重循环动态规划计算最大得分for (int x1 = 0; x1 <= b[1]; x1++){for (int x2 = 0; x2 <= b[2]; x2++){for (int x3 = 0; x3 <= b[3]; x3++){for (int x4 = 0; x4 <= b[4]; x4++){// 计算当前位置：1 + 1步卡片数 + 2步卡片数*2 + 3步卡片数*3 + 4步卡片数*4int current_pos = 1 + x1 + x2 * 2 + x3 * 3 + x4 * 4;int current_score = a[current_pos];// 状态转移：尝试使用不同步长的卡片if (x1 != 0){dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], dp[x1 - 1][x2][x3][x4] + current_score);}if (x2 != 0){dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4],dp[x1][x2 - 1][x3][x4] + current_score);}if (x3 != 0){dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4],dp[x1][x2][x3 - 1][x4] + current_score);}if (x4 != 0){dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4],dp[x1][x2][x3][x4 - 1] + current_score);}}}}}// 输出使用所有卡片后的最大得分cout << dp[b[1]][b[2]][b[3]][b[4]];return 0;
}
【运行结果】
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
73