✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东-2026.03.14-第二套

第二套比第一套更像标准机考。第一题是带两种资源约束的选择型动态规划，重点在于“先保证件数最多，再在这些方案里取油耗最小”；第二题数据范围不大，但状态设计要清楚，核心是把“选若干个互不相交子串”压成一个左到右的子集 DP。

题目一：双通道派送计划

这题表面像贪心选包裹，实际上只要一件包裹有两种完成方式，局部选择就很容易把全局最优做坏。稳定做法是把“已送件数 + 已用通行证”作为状态，维护达到这个状态时的最小燃料。

难度：中等

题目二：二进制片段分配

关键不是枚举所有区间组合，而是先把每个数字对应的二进制子串出现位置全部找出来。然后按从左到右的顺序做子集 DP，记录某个集合已经匹配完时最早能停在哪里，就能把指数爆炸压到 。

难度：中等

1. 双通道派送计划

问题描述

本题是京东 2025.11.08 第 1 题的原题。

L 小姐正在安排一批高优先级物资的运输。共有 个包裹，每个包裹都有两种送达方式：

• 常规航线：消耗较多燃料。
• 快速通道：会额外消耗一张通行证，但燃料开销可能更低。

运输船当前最多可使用 单位燃料，以及 张通行证。每个包裹至多选择一种方式派送，也可以不派送。

现在希望先让送达的包裹数量尽可能多；在此基础上，再让总燃料消耗尽可能小。

请输出最多能送达多少个包裹，以及对应的最小燃料消耗。

输入格式

第一行输入三个整数 、、，分别表示包裹数量、燃料上限和通行证数量。

接下来 行，每行输入两个整数 、：

• 表示第 个包裹走常规航线需要消耗的燃料。
• 表示第 个包裹走快速通道需要消耗的燃料。

输出格式

输出一行两个整数，分别表示：

• 最多可送达的包裹数量。
• 在达到这个数量的前提下，最小的燃料消耗。

样例输入 1

3 20 1
8 5
7 4
10 6

样例输出 1

2 12

样例说明 1

最多只能完成 个包裹。此时可以让前两个包裹分别消耗 和 单位燃料，总油耗为 。

样例输入 2

4 25 2
10 6
8 5
12 7
9 6

样例输出 2

3 20

样例说明 2

可以完成 个包裹，并把总燃料控制到 。

数据范围

样例	解释说明
样例1	在燃料和通行证都有限的情况下，最优策略只能送完 个包裹，其中最省油的方案总消耗为 。
样例2	第二组样例中可以做到送完 个包裹，同时保留最小油耗 。

题解

如果只问“最小燃料消耗”，或者只问“最多送多少个包裹”，都还比较像普通背包。

但这题有两个目标，而且优先级非常明确：

1. 先最大化送达数量。
2. 再在这些方案里最小化燃料消耗。

这就意味着不能用单纯的贪心去挑“当前最便宜”的包裹，因为某个局部便宜的选择，可能会浪费掉后面更关键的通行证名额。

状态怎么设

设 表示：

• 恰好送达了 个包裹。
• 一共用了 张通行证。
• 在这种情况下，所需的最小燃料。

初始时：

• 
• 其他状态都设成无穷大。

怎么转移

枚举每个包裹时，有两种合法选择：

• 走常规航线：燃料增加 ，送达数量加 ，通行证数不变。
• 走快速通道：燃料增加 ，送达数量加 ，通行证数加 。

因此从 可以转移到：

为了保证每个包裹只被使用一次，枚举 和 时都要倒序更新。

为什么这样就满足双目标

因为我们对每个状态都只保留“最小燃料”。

最后从大到小枚举可送达数量 ：

• 只要存在某个 ，使得 ，说明数量 可行。
• 由于我们是从大到小找的，第一个可行的 就是最大送达数量。
• 在这个 下，再取所有可行 里的最小燃料，就是题目要的第二目标。

复杂度分析

状态规模是 ，每个包裹都要枚举一遍这些状态。

总时间复杂度为 ，空间复杂度为 。

在 、 的范围内完全可行。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()
INF = 10**18


def solve() -> None:
    n, x, y = map(int, input().split())
    arr = [tuple(map(int, input().split())) for _ in range(n)]

    # dp[k][t] 表示送达 k 个包裹、使用 t 张通行证时的最小燃料。
    dp = [[INF] * (y + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for a, b in arr:
        for k in range(n - 1, -1, -1):
            for t in range(y, -1, -1):
                cur = dp[k][t]
                if cur == INF:
                    continue

                # 当前包裹走常规航线。
                if dp[k + 1][t] > cur + a:
                    dp[k + 1][t] = cur + a

                # 当前包裹走快速通道。
                if t < y and dp[k + 1][t + 1] > cur + b:
                    dp[k + 1][t + 1] = cur + b

    for k in range(n, -1, -1):
        best = min(dp[k])
        if best <= x:
            print(k, best)
            return


if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x, y;
    cin >> n >> x >> y;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i].first >> arr[i].second;
    }

    const int INF = 1e9;
    vector<vector<int>> dp(n + 1, vector<int>(y + 1, INF));
    dp[0][0] = 0;

    for (auto [a, b] : arr) {
        for (int k = n - 1; k >= 0; --k) {
            for (int t = y; t >= 0; --t) {
                if (dp[k][t] == INF) {
                    continue;
                }

                // 当前包裹走常规航线。
                dp[k + 1][t] = min(dp[k + 1][t], dp[k][t] + a);

                // 当前包裹走快速通道。
                if (t < y) {
                    dp[k + 1][t + 1] = min(dp[k + 1][t + 1], dp[k][t] + b);
                }
            }
        }
    }

    for (int k = n; k >= 0; --k) {
        int best = INF;
        for (int t = 0; t <= y; ++t) {
            best = min(best, dp[k][t]);
        }
        if (best <= x) {
            cout << k << ' ' << best << '\n';
            return 0;
        }
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= 32 && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int value = 0;
            while (c > 32) {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int x = fs.nextInt();
        int y = fs.nextInt();

        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = fs.nextInt();
            arr[i][1] = fs.nextInt();
        }

        final int INF = 1_000_000_000;
        int[][] dp = new int[n + 1][y + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;

        for (int[] cur : arr) {
            int a = cur[0];
            int b = cur[1];
            for (int k = n - 1; k >= 0; k--) {
                for (int t = y; t >= 0; t--) {
                    if (dp[k][t] == INF)