题解 | #小红笔试#

题目链接

小红笔试

题目描述

小红参加一场笔试，共有 $n$ 道编程题，总时长为 $t$ 。

对于每道题，小红可以选择三种策略：

写正解 (A)：耗时 $t_a$ ，得分 $s_a$ 。
写暴力 (B)：耗时 $t_b$ ，得分 $s_b$ 。
放弃 (F)：耗时 $0$ ，得分 $0$ 。

请帮助小红制定一个策略，在总耗时不超过 $t$ 的前提下，获得尽可能高的总分数。你需要输出每道题的选择（'A', 'B', 或 'F'）。

解题思路

这是一个典型的分组背包问题，是动态规划（DP）的经典应用之一。

1. 问题建模

我们可以将这个问题看作是一个背包问题：

背包容量：总时长 $t$ 。
物品组：每道编程题可以看作一个“物品组”。
组内物品：每个组内有三个“物品”，分别对应三种策略（A, B, F）。每个“物品”有自己的“重量”（耗时）和“价值”（得分）。

我们的目标是从 $n$ 个物品组中，每个组至多选择一个物品放入背包，使得背包内物品的总价值（总得分）最大。

2. 动态规划设计

状态定义

我们定义 dp[i][j] 为：在只考虑前 $i$ 道题，且总用时限制为 $j$ 的情况下，所能获得的最大分数。
状态转移

对于第 $i$ 道题和时间限制 $j$ ，我们可以从三种决策中选择一个，来更新 dp[i][j] 的值：
1. 放弃 (F)：不对第 $i$ 题进行任何操作。这种情况下，最大分数等于只考虑前 $i-1$ 道题、在时间 $j$ 内能取得的最大分数。 $score_F = dp[i-1][j]$
2. 写暴力 (B)：如果当前时间 $j$ 足够（ $j \ge t_{b,i}$ ），我们可以选择写暴力。总分将是暴力得分 $s_{b,i}$ 加上用剩余时间 $j - t_{b,i}$ 去解决前 $i-1$ 道题所能得到的最大分数。 $score_B = dp[i-1][j - t_{b,i}] + s_{b,i}$
3. 写正解 (A)：同理，如果时间足够（ $j \ge t_{a,i}$ ），我们可以选择写正解。 $score_A = dp[i-1][j - t_{a,i}] + s_{a,i}$
dp[i][j] 的值就是这三者中的最大值：

$dp[i][j] = \max(score_F, score_B, score_A)$
路径记录与回溯

由于题目要求输出具体方案，我们需要在进行DP时记录下每一个状态 dp[i][j] 是由哪个决策得到的。我们可以使用一个额外的 path[i][j] 数组来存储决策（'F', 'B', 或 'A'）。

在填充完整个 dp 和 path 表后，我们从 path[n][t] 开始，根据记录的决策逐步回溯，倒序构建出每一道题的选择，最后反转得到最终答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Problem {
    int ta, sa, tb, sb;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    vector<Problem> problems(n);
    for (int i = 0; i < n; ++i) {
        cin >> problems[i].ta >> problems[i].sa >> problems[i].tb >> problems[i].sb;
    }

    vector<vector<int>> dp(n + 1, vector<int>(t + 1, 0));
    vector<vector<char>> path(n + 1, vector<char>(t + 1, 'F'));

    for (int i = 1; i <= n; ++i) {
        Problem p = problems[i - 1];
        for (int j = 0; j <= t; ++j) {
            // Default: Fail
            dp[i][j] = dp[i - 1][j];
            path[i][j] = 'F';

            // Try Brute-force
            if (j >= p.tb && dp[i - 1][j - p.tb] + p.sb > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - p.tb] + p.sb;
                path[i][j] = 'B';
            }

            // Try AC
            if (j >= p.ta && dp[i - 1][j - p.ta] + p.sa > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - p.ta] + p.sa;
                path[i][j] = 'A';
            }
        }
    }

    string result = "";
    int current_t = t;
    for (int i = n; i >= 1; --i) {
        char choice = path[i][current_t];
        result += choice;
        if (choice == 'A') {
            current_t -= problems[i - 1].ta;
        } else if (choice == 'B') {
            current_t -= problems[i - 1].tb;
        }
    }
    reverse(result.begin(), result.end());
    cout << result << endl;

    return 0;
}

import java.util.Scanner;

class Problem {
    int ta, sa, tb, sb;
    public Problem(int ta, int sa, int tb, int sb) {
        this.ta = ta;
        this.sa = sa;
        this.tb = tb;
        this.sb = sb;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int t = sc.nextInt();

        Problem[] problems = new Problem[n];
        for (int i = 0; i < n; i++) {
            problems[i] = new Problem(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        int[][] dp = new int[n + 1][t + 1];
        char[][] path = new char[n + 1][t + 1];

        for (int i = 1; i <= n; i++) {
            Problem p = problems[i - 1];
            for (int j = 0; j <= t; j++) {
                // Default: Fail
                dp[i][j] = dp[i - 1][j];
                path[i][j] = 'F';

                // Try Brute-force
                if (j >= p.tb && dp[i - 1][j - p.tb] + p.sb > dp[i][j]) {
                    dp[i][j] = dp[i - 1][j - p.tb] + p.sb;
                    path[i][j] = 'B';
                }

                // Try AC
                if (j >= p.ta && dp[i - 1][j - p.ta] + p.sa > dp[i][j]) {
                    dp[i][j] = dp[i - 1][j - p.ta] + p.sa;
                    path[i][j] = 'A';
                }
            }
        }

        StringBuilder result = new StringBuilder();
        int currentT = t;
        for (int i = n; i >= 1; i--) {
            char choice = path[i][currentT];
            result.append(choice);
            if (choice == 'A') {
                currentT -= problems[i - 1].ta;
            } else if (choice == 'B') {
                currentT -= problems[i - 1].tb;
            }
        }
        System.out.println(result.reverse().toString());
    }
}

import sys

def solve():
    try:
        n, t = map(int, sys.stdin.readline().split())
        problems = []
        for _ in range(n):
            problems.append(list(map(int, sys.stdin.readline().split())))
    except (IOError, ValueError):
        return

    dp = [[0] * (t + 1) for _ in range(n + 1)]
    path = [['F'] * (t + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        ta, sa, tb, sb = problems[i-1]
        for j in range(t + 1):
            # Default: Fail
            dp[i][j] = dp[i-1][j]
            path[i][j] = 'F'

            # Try Brute-force
            if j >= tb and dp[i-1][j-tb] + sb > dp[i][j]:
                dp[i][j] = dp[i-1][j-tb] + sb
                path[i][j] = 'B'

            # Try AC
            if j >= ta and dp[i-1][j-ta] + sa > dp[i][j]:
                dp[i][j] = dp[i-1][j-ta] + sa
                path[i][j] = 'A'

    result = []
    current_t = t
    for i in range(n, 0, -1):
        choice = path[i][current_t]
        result.append(choice)
        if choice == 'A':
            current_t -= problems[i-1][0]
        elif choice == 'B':
            current_t -= problems[i-1][2]
    
    print("".join(reversed(result)))

solve()

算法及复杂度

算法：动态规划 (分组背包)
时间复杂度： $O(N \cdot T)$ 。
- 我们需要填充一个大小为 $N \times T$ 的DP表，每个状态的计算是常数时间。
空间复杂度： $O(N \cdot T)$ 。
- 我们需要 $O(N \cdot T)$ 的空间来存储 dp 表和 path 表。