题解：乌龟棋最大得分（多维 DP）

一、解题核心思路

本题的核心是 通过动态规划记录卡片使用状态，最大化路径得分。由于卡片仅包含 $1,2,3,4$ 四种类型，且每种类型的张数最多 $40$ 张，适合用 四维 DP 状态 表示每种卡片的使用次数，避免枚举所有卡片使用顺序（复杂度过高）。

二、关键分析

1. 状态定义： 设 $dp[c1][c2][c3][c4]$ 表示使用 $c1$ 张 $1$ 型卡片、$c2$ 张 $2$ 型卡片、$c3$ 张 $3$ 型卡片、$c4$ 张 $4$ 型卡片时，能获得的 最大得分。

   • 维度意义：四种卡片的使用次数直接决定了当前所在的棋盘位置，无需额外记录位置信息。

2. 当前位置计算： 起点为第 $1$ 格，使用 $c1$ 张 $1$ 型卡片、$c2$ 张 $2$ 型卡片、$c3$ 张 $3$ 型卡片、$c4$ 张 $4$ 型卡片后，所在位置为：

   $$pos = 1 + 1 \times c1 + 2 \times c2 + 3 \times c3 + 4 \times c4 $$

   （因为每张卡片对应爬行的格子数，累加后从起点 $1$ 出发）。

3. 状态转移： 对于每个状态 $dp[c1][c2][c3][c4]$，当前位置为 $pos$，可通过使用剩余的任意一种卡片转移到下一个状态：

   • 若 $c1 < cnt[1]$（还有 $1$ 型卡片剩余）：下一个状态为 $dp[c1+1][c2][c3][c4]$，得分加上 $a[pos]$（因为使用 $1$ 型卡片后会走到 $pos+1$ 格，$a[pos]$ 是第 $pos+1$ 格的分数，数组按 $0$-based 存储时需注意索引转换）。
   • 同理，对 $c2 < cnt[2]$、$c3 < cnt[3]$、$c4 < cnt[4]$ 分别处理，取最大值更新下一个状态。

4. 初始化： 初始状态为 $dp[0][0][0][0] = a[0]$（起点是第 $1$ 格，对应数组 $0$-based 索引的第 $0$ 个元素，自动获得该格分数）。

5. 答案： 最终状态为 $dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]$，其中 $cnt[k]$ 是第 $k$ 型卡片的总张数（$k=1,2,3,4$）。

三、具体解题步骤

1. 统计卡片数量：遍历输入的卡片数组，统计 $1,2,3,4$ 四种类型的卡片各有多少张（存储在 $cnt[1..4]$ 中）。
2. 初始化 DP 数组：创建四维数组 $dp[cnt1+1][cnt2+1][cnt3+1][cnt4+1]$，初始值为 $0$，并设置 $dp[0][0][0][0] = a[0]$。
3. 填充 DP 数组：枚举所有可能的 $c1, c2, c3, c4$ 组合，计算当前位置 $pos$，并通过四种卡片的剩余情况转移状态，更新最大得分。
4. 输出结果：输出最终状态的最大得分。

四、完整代码实现

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    vector<int> cnt(5, 0); // cnt[1]~cnt[4] 存储四种卡片的数量
    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    // 初始化四维 DP 数组，维度为 (cnt1+1) x (cnt2+1) x (cnt3+1) x (cnt4+1)
    int dp[cnt[1]+1][cnt[2]+1][cnt[3]+1][cnt[4]+1];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0] = a[0]; // 起点第1格的分数

    // 枚举所有可能的卡片使用次数组合
    for (int c1 = 0; c1 <= cnt[1]; ++c1) {
        for (int c2 = 0; c2 <= cnt[2]; ++c2) {
            for (int c3 = 0; c3 <= cnt[3]; ++c3) {
                for (int c4 = 0; c4 <= cnt[4]; ++c4) {
                    // 计算当前所在位置（1-based）
                    int pos = 1 + c1*1 + c2*2 + c3*3 + c4*4;
                    if (pos > N) continue; // 超出棋盘范围，跳过（题目保证最终能到终点，此句可选）

                    // 尝试使用1型卡片
                    if (c1 < cnt[1]) {
                        int next_pos = pos + 1;
                        dp[c1+1][c2][c3][c4] = max(
                            dp[c1+1][c2][c3][c4],
                            dp[c1][c2][c3][c4] + a[next_pos - 1] // a是0-based
                        );
                    }
                    // 尝试使用2型卡片
                    if (c2 < cnt[2]) {
                        int next_pos = pos + 2;
                        dp[c1][c2+1][c3][c4] = max(
                            dp[c1][c2+1][c3][c4],
                            dp[c1][c2][c3][c4] + a[next_pos - 1]
                        );
                    }
                    // 尝试使用3型卡片
                    if (c3 < cnt[3]) {
                        int next_pos = pos + 3;
                        dp[c1][c2][c3+1][c4] = max(
                            dp[c1][c2][c3+1][c4],
                            dp[c1][c2][c3][c4] + a[next_pos - 1]
                        );
                    }
                    // 尝试使用4型卡片
                    if (c4 < cnt[4]) {
                        int next_pos = pos + 4;
                        dp[c1][c2][c3][c4+1] = max(
                            dp[c1][c2][c3][c4+1],
                            dp[c1][c2][c3][c4] + a[next_pos - 1]
                        );
                    }
                }
            }
        }
    }

    // 最终状态：使用完所有卡片
    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;

    return 0;
}

五、代码解释

1. 卡片统计：用 cnt[1..4] 统计四种卡片的数量，简化 DP 维度定义。
2. DP 数组初始化：四维数组直接用栈空间分配（因为每种卡片最多 $40$ 张，$41^4=2.8 \times 10^6$，栈空间足够），初始状态为起点分数。
3. 状态转移：枚举所有卡片使用组合，计算当前位置，再通过使用剩余卡片转移到下一个位置，累加对应格子的分数，取最大值更新状态。
4. 索引转换：棋盘格子是 $1$-based，数组存储是 $0$-based，因此 a[next_pos - 1] 对应下一个位置的分数。

六、复杂度分析

• 时间复杂度：$O(c1 \times c2 \times c3 \times c4)$，其中 $c1,c2,c3,c4$ 分别是四种卡片的最大张数（各 $40$）。总操作数为 $41 \times 41 \times 41 \times 41 \approx 2.8 \times 10^6$，效率极高。
• 空间复杂度：$O(c1 \times c2 \times c3 \times c4)$，约 $2.8 \times 10^6$ 个整数，空间开销可控。

该方法通过多维 DP 高效枚举所有卡片使用状态，确保找到最大得分，完全适配题目数据范围。