洛谷 - P1541 乌龟棋

题面

题目背景

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

题目描述

乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 $M$ 张爬行卡片，分成 4 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1, 2, 3, 4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 $1$ 行 $2$ 个正整数 $N, M$，分别表示棋盘格子数和爬行卡片数。

第 $2$ 行 $N$ 个非负整数，$a_1, a_2, \ldots, a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。

第 $3$ 行 $M$ 个整数，$b_1, b_2, \ldots, b_M$，表示 $M$ 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

73

样例解释 #1

思路

多维 DP 经典题。

可以考虑设置 $4$ 个维度，每个维度分别记录 $1, 2, 3, 4$ 号卡片的状态，而当前所在的格就是 $a_{i + 2j + 3k + 4l}$。

得转移方程如下：

$$\begin{aligned} & f_{i, j, k, l} = \max(f_{i, j, k, l}, f_{i - 1, j, k, l}) + a_{i + 2j + 3k + 4l} & (i > 0) \\ & f_{i, j, k, l} = \max(f_{i, j, k, l}, f_{i, j - 1, k, l}) + a_{i + 2j + 3k + 4l} & (j > 0) \\ & f_{i, j, k, l} = \max(f_{i, j, k, l}, f_{i, j, k - 1, l}) + a_{i + 2j + 3k + 4l} & (k > 0) \\ & f_{i, j, k, l} = \max(f_{i, j, k, l}, f_{i, j, k, l - 1}) + a_{i + 2j + 3k + 4l} & (l > 0) \\ \end{aligned}$$

其中 $i \in [0, b_1], j \in [0, b_2], k \in [0, b_3], l \in [0, b_4]$。

代码

#include <algorithm>
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 355,
          M = 125;

int n, m, a[N], b[5], f[M][M][M][M];

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        b[x]++;
    }

    f[0][0][0][0] = a[1];
    for (int i = 0; i <= b[1]; i++) {
        for (int j = 0; j <= b[2]; j++) {
            for (int k = 0; k <= b[3]; k++) {
                for (int l = 0; l <= b[4]; l++) {
                    f[i][j][k][l] = std::max({i ? f[i - 1][j][k][l] : 0,
                                              j ? f[i][j - 1][k][l] : 0,
                                              k ? f[i][j][k - 1][l] : 0,
                                              l ? f[i][j][k][l - 1] : 0}) +
                                    a[1 + i + j * 2 + k * 3 + l * 4];
                }
            }
        }
    }

    cout << f[b[1]][b[2]][b[3]][b[4]] << endl;

    return 0;
}