小红笔试

[题目链接](https://www.nowcoder.com/practice/a165da3628d6438495da2f789fb3d3c0)

思路

本题是一个经典的分组背包问题。每道题有三种选择：写正解（A）、写暴力（B）、放弃（F），需要在总时间 内最大化总得分，并输出具体方案。

建模

将总时间视为背包容量，每道题视为一组物品：

  • A：耗时 ，得分
  • B：耗时 ，得分
  • F：耗时 ，得分

每组恰好选一个，这就是标准的分组背包。

DP 定义与转移

定义 为前 道题、耗时恰好为 时的最大得分。转移方程：

$$

方案回溯

在 DP 过程中，记录每个状态 的最优选择（ 表示 F， 表示 A， 表示 B）。最终从 出发，按 从 到 逆序回溯，还原完整的策略字符串。

空间优化

对于 C++/Java/JS，可以使用二维数组直接存储。对于 Python，为了避免 TLE，使用滚动数组：每一轮复制上一轮的 数组，然后在副本上更新 A 和 B 的选择，避免使用二维列表的嵌套开销。

复杂度分析

  • 时间复杂度：，每道题对每个容量做常数次比较。
  • 空间复杂度：，存储 DP 数组和选择数组。使用滚动数组可将 DP 数组降为 ，但选择数组仍需 。

代码

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

int main(){
    int n, T;
    scanf("%d%d", &n, &T);
    vector<int> ta(n), sa(n), tb(n), sb(n);
    for(int i = 0; i < n; i++){
        scanf("%d%d%d%d", &ta[i], &sa[i], &tb[i], &sb[i]);
    }

    vector<vector<int>> dp(n+1, vector<int>(T+1, 0));
    vector<vector<int>> choice(n, vector<int>(T+1, 0));

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= T; j++){
            dp[i+1][j] = dp[i][j];
            choice[i][j] = 0;
            if(j >= ta[i] && dp[i][j - ta[i]] + sa[i] > dp[i+1][j]){
                dp[i+1][j] = dp[i][j - ta[i]] + sa[i];
                choice[i][j] = 1;
            }
            if(j >= tb[i] && dp[i][j - tb[i]] + sb[i] > dp[i+1][j]){
                dp[i+1][j] = dp[i][j - tb[i]] + sb[i];
                choice[i][j] = 2;
            }
        }
    }

    string ans(n, 'F');
    int j = T;
    for(int i = n-1; i >= 0; i--){
        if(choice[i][j] == 1){
            ans[i] = 'A';
            j -= ta[i];
        } else if(choice[i][j] == 2){
            ans[i] = 'B';
            j -= tb[i];
        }
    }

    printf("%s\n", ans.c_str());
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), T = sc.nextInt();
        int[] ta = new int[n], sa = new int[n], tb = new int[n], 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];
        int[][] choice = new int[n][T + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= T; j++) {
                dp[i + 1][j] = dp[i][j];
                choice[i][j] = 0;
                if (j >= ta[i] && dp[i][j - ta[i]] + sa[i] > dp[i + 1][j]) {
                    dp[i + 1][j] = dp[i][j - ta[i]] + sa[i];
                    choice[i][j] = 1;
                }
                if (j >= tb[i] && dp[i][j - tb[i]] + sb[i] > dp[i + 1][j]) {
                    dp[i + 1][j] = dp[i][j - tb[i]] + sb[i];
                    choice[i][j] = 2;
                }
            }
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) ans.append('F');
        int j = T;
        for (int i = n - 1; i >= 0; i--) {
            if (choice[i][j] == 1) {
                ans.setCharAt(i, 'A');
                j -= ta[i];
            } else if (choice[i][j] == 2) {
                ans.setCharAt(i, 'B');
                j -= tb[i];
            }
        }

        System.out.println(ans.toString());
    }
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    ta = [0]*n; sa = [0]*n; tb = [0]*n; sb = [0]*n
    for i in range(n):
        ta[i] = int(data[idx]); idx += 1
        sa[i] = int(data[idx]); idx += 1
        tb[i] = int(data[idx]); idx += 1
        sb[i] = int(data[idx]); idx += 1

    dp = [0] * (T + 1)
    choice = [bytearray(T + 1) for _ in range(n)]

    for i in range(n):
        tai = ta[i]; sai = sa[i]; tbi = tb[i]; sbi = sb[i]
        ci = choice[i]
        new_dp = dp[:]
        for j in range(T + 1):
            if j >= tai:
                v = dp[j - tai] + sai
                if v > new_dp[j]:
                    new_dp[j] = v
                    ci[j] = 1
            if j >= tbi:
                v = dp[j - tbi] + sbi
                if v > new_dp[j]:
                    new_dp[j] = v
                    ci[j] = 2
        dp = new_dp

    ans = ['F'] * n
    j = T
    for i in range(n - 1, -1, -1):
        c = choice[i][j]
        if c == 1:
            ans[i] = 'A'
            j -= ta[i]
        elif c == 2:
            ans[i] = 'B'
            j -= tb[i]

    sys.stdout.write(''.join(ans) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, T] = lines[0].split(' ').map(Number);
    const ta = [], sa = [], tb = [], sb = [];
    for (let i = 0; i < n; i++) {
        const parts = lines[i + 1].split(' ').map(Number);
        ta.push(parts[0]); sa.push(parts[1]);
        tb.push(parts[2]); sb.push(parts[3]);
    }

    const dp = Array.from({length: n + 1}, () => new Int32Array(T + 1));
    const choice = Array.from({length: n}, () => new Int8Array(T + 1));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= T; j++) {
            dp[i + 1][j] = dp[i][j];
            choice[i][j] = 0;
            if (j >= ta[i] && dp[i][j - ta[i]] + sa[i] > dp[i + 1][j]) {
                dp[i + 1][j] = dp[i][j - ta[i]] + sa[i];
                choice[i][j] = 1;
            }
            if (j >= tb[i] && dp[i][j - tb[i]] + sb[i] > dp[i + 1][j]) {
                dp[i + 1][j] = dp[i][j - tb[i]] + sb[i];
                choice[i][j] = 2;
            }
        }
    }

    const ans = new Array(n).fill('F');
    let j = T;
    for (let i = n - 1; i >= 0; i--) {
        if (choice[i][j] === 1) {
            ans[i] = 'A';
            j -= ta[i];
        } else if (choice[i][j] === 2) {
            ans[i] = 'B';
            j -= tb[i];
        }
    }

    console.log(ans.join(''));
});