P1541 [NOIP 2010 提高组] 乌龟棋 - 洛谷

题目背景

NOIP2010 提高组 T2

题目描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 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 张爬行卡片。

输出格式

一个整数，表示小明最多能得到的分数。

输入输出样例

输入 #1复制

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

输出 #1复制

73

说明/提示

每个测试点 1s。

小明使用爬行卡片顺序为 1,1,3,1,2，得到的分数为 6+10+14+8+18+17=73。注意，由于起点是 1，所以自动获得第 1 格的分数 6。

对于 30% 的数据有 1≤N≤30,1≤M≤12。

对于 50% 的数据有 1≤N≤120,1≤M≤50，且 4 种爬行卡片，每种卡片的张数不会超过 20。

对于 100% 的数据有 1≤N≤350,1≤M≤120，且 4 种爬行卡片，每种卡片的张数不会超过 40；0≤ai​≤100,1≤i≤N,1≤bi​≤4,1≤i≤M。

思路;

代码：
 

#include<bits/stdc++.h>
using namespace std;const int MAXN = 41;  // 每种卡片最多40张（题目限制）
int dp[MAXN][MAXN][MAXN][MAXN];  // 四维DP数组，记录状态
int num[351];  // 存储棋盘各格子的分数（下标1~n）
int g[5];  // 统计四种卡片的数量（g[1]~g[4]对应类型1~4）
int n, m, x;  // n：棋盘长度，m：卡片总数，x：临时存储卡片类型int main() {ios::sync_with_stdio(false);  // 加速输入输出cin >> n >> m;  // 读取棋盘长度和卡片总数// 读取棋盘各格子的分数（第1格到第n格）for (int i = 1; i <= n; i++) {cin >> num[i];}// 初始状态：未使用任何卡片时，位于第1格，得分为num[1]dp[0][0][0][0] = num[1];// 统计四种卡片的数量（g[1]~g[4]）for (int i = 1; i <= m; i++) {cin >> x;g[x]++;}// 枚举所有可能的卡片使用次数组合（a:1步卡，b:2步卡，c:3步卡，d:4步卡）for (int a = 0; a <= g[1]; a++) {for (int b = 0; b <= g[2]; b++) {for (int c = 0; c <= g[3]; c++) {for (int d = 0; d <= g[4]; d++) {int pos = 1 + a + 2*b + 3*c + 4*d;if (a > 0) {  // 最后一步用了1步卡dp[a][b][c][d] = max(dp[a][b][c][d], dp[a-1][b][c][d] + num[pos]);}if (b > 0) {  // 最后一步用了2步卡dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b-1][c][d] + num[pos]);}if (c > 0) {  // 最后一步用了3步卡dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c-1][d] + num[pos]);}if (d > 0) {  // 最后一步用了4步卡dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d-1] + num[pos]);}}}}}cout << dp[g[1]][g[2]][g[3]][g[4]] << endl;return 0;
}