HIGH90 小红笔试

题目描述

小红参加一场有 道题的编程笔试，总时长为 分钟。对于第 道题，她有三种选择：

  1. 写出正确算法：耗时 ，得分 。
  2. 写出暴力算法：耗时 ，得分 。
  3. 放弃此题：耗时 ，得分 。

要求规划一个做题方案，使得在总耗时不超过 的前提下，总得分最大。并输出这个方案。

解题思路

这是一个典型的分组背包问题。我们可以将总时长 视作背包的容量，每道题的得分视作物品的价值，做题耗时视作物品的重量。

1. 模型抽象

  • 背包容量：总时长 。
  • 物品组：共 个组，每道题构成一个独立的组。
  • 组内物品：对于第 道题（第 组），组内有三个互斥的“物品”可供选择，分别对应三种策略：
    1. 物品 A (正确算法): 重量 ，价值 。
    2. 物品 B (暴力算法): 重量 ，价值 。
    3. 物品 F (放弃): 重量 ，价值 。
  • 约束：每组（每道题）最多只能选择一个“物品”（一种策略）。
  • 目标：最大化总价值（总得分）。

2. 状态定义

由于本题不仅要求最大分值，还需要输出具体的方案，因此我们需要一个能够回溯路径的DP表。 我们定义一个二维数组 ， 表示：在考虑前 道题，且总耗时不超过 分钟的情况下，能获得的最大总分数。

3. 状态转移方程

当我们考虑第 道题，且当前可用时间为 时，我们的决策是基于第 道题的状态：

  1. 放弃第 题 (策略F)：不花费时间，得分也不增加。此时的最大分数等于只考虑前 题、耗时为 的分数。

  2. 写第 题的暴力算法 (策略B)：前提是 。此时的最大分数等于只考虑前 题、耗时为 的分数，加上本题暴力解的得分。

  3. 写第 题的正确算法 (策略A)：前提是 。此时的最大分数等于只考虑前 题、耗时为 的分数，加上本题正确解的得分。

我们将这三种情况取最大值，就是 的最终值。

4. 方案回溯

在填充完整个 表后， 就是最终的最大得分。为了找出具体的方案，我们需要从 开始倒推：

  1. 从 开始。
  2. 对于当前的 ，检查它是如何从 转移过来的：
    • 如果 且 ，说明第 题选择了策略 A。记录下选择，并将时间更新为 。
    • 否则，如果 且 ，说明第 题选择了策略 B。记录下选择，并将时间更新为 。
    • 否则，必然是 ，说明第 题选择了策略 F (放弃)。记录下选择，时间 不变。
  3. 令 ，重复步骤2，直到 。
  4. 由于是倒序推导，最后需要将记录的方案反转得到最终答案。

代码实现

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

using namespace std;

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

int main() {
    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));

    // 动态规划求解
    for (int i = 1; i <= n; ++i) {
        int ta = problems[i - 1].ta;
        int sa = problems[i - 1].sa;
        int tb = problems[i - 1].tb;
        int sb = problems[i - 1].sb;

        for (int j = 0; j <= T; ++j) {
            // 策略C：放弃
            dp[i][j] = dp[i - 1][j];
            // 策略B：暴力
            if (j >= tb) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - tb] + sb);
            }
            // 策略A：正解
            if (j >= ta) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - ta] + sa);
            }
        }
    }

    // 回溯寻找方案
    string result = "";
    int currentTime = T;
    for (int i = n; i >= 1; --i) {
        int ta = problems[i - 1].ta;
        int sa = problems[i - 1].sa;
        int tb = problems[i - 1].tb;
        int sb = problems[i - 1].sb;

        if (currentTime >= ta && dp[i][currentTime] == dp[i - 1][currentTime - ta] + sa) {
            result += 'A';
            currentTime -= ta;
        } else if (currentTime >= tb && dp[i][currentTime] == dp[i - 1][currentTime - tb] + sb) {
            result += 'B';
            currentTime -= tb;
        } else {
            result += 'F';
        }
    }

    reverse(result.begin(), result.end());
    cout << result << endl;

    return 0;
}

import java.util.Scanner;

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

        int[] ta = new int[n];
        int[] sa = new int[n];
        int[] tb = new int[n];
        int[] sb = new int[n];

        for (int i = 0; i < n; i++) {
            ta[i] = sc.nextInt();
            sa[i] = sc.nextInt();
            tb[i] = sc.nextInt();
            sb[i] = sc.nextInt();
        }

        int[][] dp = new int[n + 1][T + 1];

        // 动态规划求解
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= T; j++) {
                // 策略C：放弃
                dp[i][j] = dp[i - 1][j];
                // 策略B：暴力
                if (j >= tb[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - tb[i - 1]] + sb[i - 1]);
                }
                // 策略A：正解
                if (j >= ta[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - ta[i - 1]] + sa[i - 1]);
                }
            }
        }

        // 回溯寻找方案
        StringBuilder result = new StringBuilder();
        int currentTime = T;
        for (int i = n; i >= 1; i--) {
            if (currentTime >= ta[i-1] && dp[i][currentTime] == dp[i-1][currentTime - ta[i-1]] + sa[i-1]) {
                result.append('A');
                currentTime -= ta[i-1];
            } else if (currentTime >= tb[i-1] && dp[i][currentTime] == dp[i-1][currentTime - tb[i-1]] + sb[i-1]) {
                result.append('B');
                currentTime -= tb[i-1];
            } else {
                result.append('F');
            }
        }

        System.out.println(result.reverse().toString());
    }
}

def main():
    n, T = map(int, input().split())
    problems = []
    for _ in range(n):
        problems.append(list(map(int, input().split())))
    
    # dp[i][j]: 考虑前i道题，用时j的最大分数
    dp = [[0] * (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):
            # 策略C: 放弃
            dp[i][j] = dp[i - 1][j]
            # 策略B: 暴力
            if j >= tb:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - tb] + sb)
            # 策略A: 正解
            if j >= ta:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - ta] + sa)

    # 回溯寻找方案
    result = []
    current_time = T
    for i in range(n, 0, -1):
        ta, sa, tb, sb = problems[i - 1]
        
        if current_time >= ta and dp[i][current_time] == dp[i-1][current_time-ta] + sa:
            result.append('A')
            current_time -= ta
        elif current_time >= tb and dp[i][current_time] == dp[i-1][current_time-tb] + sb:
            result.append('B')
            current_time -= tb
        else:
            result.append('F')
    
    print("".join(reversed(result)))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 分组背包 (动态规划)
  • 时间复杂度: 。填充 表需要两层循环，外层遍历 道题，内层遍历时间 。回溯方案的时间复杂度为 。因此总时间复杂度为 。
  • 空间复杂度: 。需要 的空间存储输入数据，以及 的空间来存储用于回溯的 表。