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

// P1541 的参照物：DFS 枚举「下一张出哪种卡」。
//
// 它不记忆化、也不用「位置能算出来」这件事 —— 就是把所有出牌顺序走一遍。
// 分支 4 层深 M ⇒ 卡片一多就跑不完，所以生成器把 M 压到 10 以内。
// ⇒ 它和正解一个字都不共享。

#include <bits/stdc++.h>
using namespace std;

int n, a[355], cnt[5], best;

void dfs(int pos, int sum) {
    best = max(best, sum);
    for (int d = 1; d <= 4; d++)
        if (cnt[d] && pos + d <= n) {
            cnt[d]--;
            dfs(pos + d, sum + a[pos + d]);
            cnt[d]++;
        }
}

int main() {
    int m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%d", &a[i]) != 1) return 0;
    for (int i = 0; i < m; i++) {
        int x;
        if (scanf("%d", &x) != 1) return 0;
        cnt[x]++;
    }
    best = 0;
    dfs(1, a[1]);
    printf("%d\n", best);
    return 0;
}

// P1541 [NOIP 2010 提高组] 乌龟棋 —— ★ 这一版就能 AC。
//
// ★★ 关键的一步：**状态里不需要「现在站在第几格」这一维。**
//   四种卡片各用了几张（`i, j, k, l`），位置就被**算死**了：
//       pos = 1 + 1×i + 2×j + 3×k + 4×l
//   ⇒ 这就是第 25 章上半场那件事推到四维：**多一维费用就多一层循环**，
//     而这道题的「费用」是四种卡片各自的张数。
//
// 状态数 = (c1+1)(c2+1)(c3+1)(c4+1) ≤ 41⁴ ≈ 282 万，每个状态四个转移 ⇒ 一千万出头。
//
// ⚠ 两处最容易漏：
//   ① **起点那一格的分数是白送的**（`f[0][0][0][0] = a[1]`，不是 0）；
//   ② 题面那句「保证到达终点时刚好用光 M 张卡片」⇒ 答案就是**全用完**那个状态，
//      而且 `pos` 不会跑出棋盘 —— 下面这句 `a[pos]` **正是靠它才敢直接读**。
//      ⚠ 页面第 ④ 步量过：那句保证挡住的是**越界**，不是**答案** ——
//        把读法改成「跑出棋盘算 0」之后，故意违反它的 300 轮里答案一个字都没变
//        （其中 98 轮真的跑出了棋盘）。

#include <bits/stdc++.h>
using namespace std;

int a[355];
int f[41][41][41][41];
int cnt[5];

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%d", &a[i]) != 1) return 0;
    for (int i = 0; i < m; i++) {
        int x;
        if (scanf("%d", &x) != 1) return 0;
        cnt[x]++;
    }

    for (int i = 0; i <= cnt[1]; i++)
        for (int j = 0; j <= cnt[2]; j++)
            for (int k = 0; k <= cnt[3]; k++)
                for (int l = 0; l <= cnt[4]; l++) {
                    if (i + j + k + l == 0) { f[0][0][0][0] = a[1]; continue; }
                    int pos = 1 + i + 2 * j + 3 * k + 4 * l;
                    int best = -1;
                    if (i) best = max(best, f[i - 1][j][k][l]);
                    if (j) best = max(best, f[i][j - 1][k][l]);
                    if (k) best = max(best, f[i][j][k - 1][l]);
                    if (l) best = max(best, f[i][j][k][l - 1]);
                    f[i][j][k][l] = best + a[pos];
                }
    printf("%d\n", f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
    return 0;
}

// ✗ P1541 的第一个坑：忘了起点那一格的分数。
//
// 题面专门提醒过：「乌龟棋子**自动获得起点格子的分数**」——
// 而 DP 的初值写成 `f[0][0][0][0] = 0` 是最自然的动作。
//
// ★ 它「算了什么」能一句话说死：**答案恒好少 a[1]**，一分不多一分不少。
//   ⇒ 300 轮里「它 + a[1] = 正解」逐组成立；而它被抓的轮数 ≡ `a[1] > 0` 的轮数。
//   （[第 22 章 P1091](/sol/p1091/) 那个「恒好少 1」的同款。）

#include <bits/stdc++.h>
using namespace std;

int a[355];
int f[41][41][41][41];
int cnt[5];

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 1; i <= n; i++) if (scanf("%d", &a[i]) != 1) return 0;
    for (int i = 0; i < m; i++) {
        int x;
        if (scanf("%d", &x) != 1) return 0;
        cnt[x]++;
    }

    for (int i = 0; i <= cnt[1]; i++)
        for (int j = 0; j <= cnt[2]; j++)
            for (int k = 0; k <= cnt[3]; k++)
                for (int l = 0; l <= cnt[4]; l++) {
                    if (i + j + k + l == 0) { f[0][0][0][0] = 0; continue; }   // ✗ 少了 a[1]
                    int pos = 1 + i + 2 * j + 3 * k + 4 * l;
                    int best = -1;
                    if (i) best = max(best, f[i - 1][j][k][l]);
                    if (j) best = max(best, f[i][j - 1][k][l]);
                    if (k) best = max(best, f[i][j][k - 1][l]);
                    if (l) best = max(best, f[i][j][k][l - 1]);
                    f[i][j][k][l] = best + a[pos];
                }
    printf("%d\n", f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
    return 0;
}