科普日初中组第二题记忆化搜索做法

_Manstein_ · 2025-05-03 17:08:46 · 题解

前言

在解决本题时，观察到多数题解采用贪心策略。为提供不同的解题思路，本文提出一种记忆化搜索的方法，通过状态记忆避免重复计算，有效提升效率。

思路分析

核心思想

通过DFS遍历所有可能的选择方案，同时利用DP数组记录中间状态的最优结果，避免重复搜索。每个状态记录当前处理到第i个位置时的不同选择情况，从而实现状态转移的快速决策。

状态定义

dp[i][j]：表示处理到第i个操作时，当前状态为j时的最大收益增量。
- j=0：只能选择第v[i]+1杯（当v[i]杯为空且v[i]+1杯有剩余）。
- j=1：只能选择第v[i]杯（当v[i]+1杯为空且v[i]杯有剩余）。
- j=2：v[i]和v[i]+1杯均为满，小奶龙喝下果汁（sum+1）。
- j=3：两杯均有剩余，需决策选择哪一杯（或按顺序尝试两种选择取最大值）。

四种决策分支

仅可选v[i]+1杯
条件：a[v[i]] == 0且a[v[i]+1] > 0
操作：选择v[i]+1杯（数量减1），递归处理i+1，记录状态dp[i][0]。
仅可选v[i]杯
条件：a[v[i]+1] == 0且a[v[i]] > 0
操作：选择v[i]杯（数量减1），递归处理i+1，记录状态dp[i][1]。
两杯均不可选
条件：a[v[i]] == 0且a[v[i]+1] == 0
操作：小奶龙喝下果汁（sum+1），递归处理i+1，记录状态dp[i][2]。
两杯均可选
条件：其他情况（两杯至少有一个有剩余）
操作：分别尝试选择v[i]+1杯和v[i]杯，取两种选择的最大值，记录状态dp[i][3]。

核心代码解析

int dfs(int sum, int i) {
    if (i > m) {  // 处理完所有操作，返回当前总和
        return sum;
    }
    int p = sum;  // 记录当前总和，用于计算收益增量
    int maxn = 0;

    // 分支1：仅可选v[i]+1杯
    if (a[v[i]] == 0 && a[v[i] + 1] > 0) {
        if (dp[i][0] != -1) return sum + dp[i][0];  // 直接返回记忆的增量
        a[v[i] + 1]--;  // 选择v[i]+1杯
        maxn = dfs(sum, i + 1);  // 递归处理下一个操作
        a[v[i] + 1]++;  // 恢复现场，以便后续分支使用
        dp[i][0] = maxn - p;  // 记录当前状态的收益增量
    }
    // 分支2：仅可选v[i]杯
    else if (a[v[i] + 1] == 0 && a[v[i]] > 0) {
        if (dp[i][1] != -1) return sum + dp[i][1];
        a[v[i]]--;
        maxn = dfs(sum, i + 1);
        a[v[i]]++;
        dp[i][1] = maxn - p;
    }
    // 分支3：两杯均不可选，sum增加
    else if (a[v[i]] == 0 && a[v[i] + 1] == 0) {
        if (dp[i][2] != -1) return sum + dp[i][2];
        maxn = dfs(sum + 1, i + 1);  
        dp[i][2] = maxn - p;
    }
    // 分支4：两杯均可选，尝试两种选择取最大值
    else {
        if (dp[i][3] != -1) return sum + dp[i][3];
        // 尝试选择v[i]+1杯
        a[v[i] + 1]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i] + 1]++;
        // 尝试选择v[i]杯
        a[v[i]]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i]]++;
        dp[i][3] = maxn - p;
    }
    return maxn;  // 返回当前分支的最大总和
}

完整赛时代码

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

int n, m, t;
int v[30005], a[30005];
int dp[30005][4];  // 动态规划表，记录各状态的收益增量

int dfs(int sum, int i) {
    if (i > m) return sum;
    int p = sum, maxn = 0;

    // 分支1：仅可选v[i]+1杯
    if (a[v[i]] == 0 && a[v[i] + 1] > 0) {
        if (dp[i][0] != -1) return sum + dp[i][0];
        a[v[i] + 1]--;
        maxn = dfs(sum, i + 1);
        a[v[i] + 1]++;
        dp[i][0] = maxn - p;
    }
    // 分支2：仅可选v[i]杯
    else if (a[v[i] + 1] == 0 && a[v[i]] > 0) {
        if (dp[i][1] != -1) return sum + dp[i][1];
        a[v[i]]--;
        maxn = dfs(sum, i + 1);
        a[v[i]]++;
        dp[i][1] = maxn - p;
    }
    // 分支3：两杯均不可选，sum增加
    else if (a[v[i]] == 0 && a[v[i] + 1] == 0) {
        if (dp[i][2] != -1) return sum + dp[i][2];
        maxn = dfs(sum + 1, i + 1);
        dp[i][2] = maxn - p;
    }
    // 分支4：两杯均可选，尝试两种选择
    else {
        if (dp[i][3] != -1) return sum + dp[i][3];
        a[v[i] + 1]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i] + 1]++;
        a[v[i]]--;
        maxn = max(maxn, dfs(sum, i + 1));
        a[v[i]]++;
        dp[i][3] = maxn - p;
    }
    return maxn;
}

int main() {
    // freopen("juice.in", "r", stdin);
    // freopen("juice.out", "w", stdout);
    cin >> t;
    while (t--) {
        memset(dp, -1, sizeof(dp));  // 初始化DP表为-1（未访问）
        cin >> m >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];  // 读取各杯初始数量
        for (int i = 1; i <= m; i++) cin >> v[i];  // 读取每个操作对应的位置
        cout << dfs(0, 1) << '\n';  // 从第一个操作开始搜索
    }
    return 0;
}