中世纪的商路

题目分析

本题是加权区间调度 + 背包的组合问题。给定 $n$ 条贸易航线，每条航线有出发时间、到达时间、商队规模和利润。要求选出若干条时间不重叠的航线，使得：

任意两条被选中的航线时间上不重叠（但一条结束时刻恰好等于另一条出发时刻是允许的）
所有被选中航线的商队规模之和不超过 $\text{maxSize}$
总利润最大化

思路讲解

第一步：排序 + 前驱计算

将所有航线按结束时间升序排序。对于排序后的每条航线 $i$ ，用二分查找找到它的"前驱" $p(i)$ ：即结束时间 $\leq$ 航线 $i$ 出发时间的最晚航线编号。这一步和经典加权区间调度完全相同。

第二步：二维 DP

定义 $dp[i][w]$ 为：只考虑前 $i$ 条航线、已使用的商队规模恰好为 $w$ 时，能获得的最大利润。

对于第 $i$ 条航线（规模为 $sz_i$ ，利润为 $pr_i$ ，前驱为 $p(i)$ ），有两种决策：

不选： $dp[i+1][w] = dp[i][w]$
选（需要 $w \geq sz_i$ ）： $dp[i+1][w] = dp[p(i)+1][w - sz_i] + pr_i$

注意选的时候，状态回退到 $p(i)+1$ 而非 $i$ ，因为必须保证时间不重叠。

取两者的最大值：

$ $dp[i+1][w] = \max\big(dp[i][w],\ dp[p(i)+1][w - sz_i] + pr_i\big)$ $

最终答案为 $\max_{0 \leq w \leq \text{maxSize}} dp[n][w]$ 。

为什么是「加权区间调度 + 背包」？

经典加权区间调度只有"选/不选"，选的话回退到前驱。本题在此基础上增加了"容量"维度（商队规模之和有上限），使其变成一个二维 DP 问题。
时间维度通过排序 + 二分解决不重叠约束，容量维度通过背包式枚举解决。

复杂度分析

时间复杂度： $O(n \cdot \text{maxSize} + n \log n)$ ，其中排序 $O(n \log n)$ ，DP 主体 $O(n \cdot \text{maxSize})$
空间复杂度： $O(n \cdot \text{maxSize})$

代码

C++
Java
Python3
JavaScript

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

int main(){
    auto readLine = [](vector<int>& v){
        string line;
        getline(cin, line);
        istringstream iss(line);
        int x;
        while(iss >> x) v.push_back(x);
    };

    vector<int> starts, ends, sizes, profits;
    readLine(starts);
    readLine(ends);
    readLine(sizes);
    readLine(profits);

    int maxSize;
    cin >> maxSize;

    int n = starts.size();

    // 按结束时间排序
    vector<array<int,4>> jobs;
    for(int i = 0; i < n; i++){
        jobs.push_back({ends[i], starts[i], sizes[i], profits[i]});
    }
    sort(jobs.begin(), jobs.end());

    vector<int> endTimes(n);
    for(int i = 0; i < n; i++) endTimes[i] = jobs[i][0];

    // 二分查找前驱
    vector<int> p(n, -1);
    for(int i = 0; i < n; i++){
        int si = jobs[i][1];
        int lo = 0, hi = i - 1, pos = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(endTimes[mid] <= si){
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        p[i] = pos;
    }

    // dp[i+1][w] = 前 i+1 条航线、已用容量 w 的最大利润
    vector<vector<long long>> dp(n + 1, vector<long long>(maxSize + 1, 0));

    for(int i = 0; i < n; i++){
        int sz = jobs[i][2];
        int pr = jobs[i][3];
        int pi = p[i];
        for(int w = 0; w <= maxSize; w++){
            dp[i+1][w] = dp[i][w];
            if(w >= sz){
                long long take = dp[pi + 1][w - sz] + pr;
                dp[i+1][w] = max(dp[i+1][w], take);
            }
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
    return 0;
}

import java.util.*;

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

        int[] starts = parseArray(sc.nextLine().trim());
        int[] ends = parseArray(sc.nextLine().trim());
        int[] sizes = parseArray(sc.nextLine().trim());
        int[] profits = parseArray(sc.nextLine().trim());
        int maxSize = Integer.parseInt(sc.nextLine().trim());

        int n = starts.length;

        int[][] jobs = new int[n][4];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{ends[i], starts[i], sizes[i], profits[i]};
        }
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

        int[] endTimes = new int[n];
        for (int i = 0; i < n; i++) endTimes[i] = jobs[i][0];

        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            int si = jobs[i][1];
            int lo = 0, hi = i - 1, pos = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (endTimes[mid] <= si) {
                    pos = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            p[i] = pos;
        }

        long[][] dp = new long[n + 1][maxSize + 1];

        for (int i = 0; i < n; i++) {
            int sz = jobs[i][2];
            int pr = jobs[i][3];
            int pi = p[i];
            for (int w = 0; w <= maxSize; w++) {
                dp[i + 1][w] = dp[i][w];
                if (w >= sz) {
                    long take = dp[pi + 1][w - sz] + pr;
                    dp[i + 1][w] = Math.max(dp[i + 1][w], take);
                }
            }
        }

        long ans = 0;
        for (int w = 0; w <= maxSize; w++) {
            ans = Math.max(ans, dp[n][w]);
        }
        System.out.println(ans);
    }

    static int[] parseArray(String line) {
        String[] parts = line.split("\\s+");
        int[] arr = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            arr[i] = Integer.parseInt(parts[i]);
        }
        return arr;
    }
}

import bisect
import sys
input = sys.stdin.readline

def main():
    starts = list(map(int, input().split()))
    ends = list(map(int, input().split()))
    sizes = list(map(int, input().split()))
    profits = list(map(int, input().split()))
    max_size = int(input())

    n = len(starts)

    # 按结束时间排序
    jobs = sorted(zip(ends, starts, sizes, profits))

    end_times = [j[0] for j in jobs]

    # 二分查找前驱
    p = [-1] * n
    for i in range(n):
        si = jobs[i][1]
        pos = bisect.bisect_right(end_times, si, 0, i) - 1
        p[i] = pos

    # dp[i+1][w] = 前 i+1 条航线、已用容量 w 的最大利润
    dp = [[0] * (max_size + 1) for _ in range(n + 1)]

    for i in range(n):
        sz = jobs[i][2]
        pr = jobs[i][3]
        pi = p[i]
        for w in range(max_size + 1):
            dp[i + 1][w] = dp[i][w]
            if w >= sz:
                take = dp[pi + 1][w - sz] + pr
                if take > dp[i + 1][w]:
                    dp[i + 1][w] = take

    print(max(dp[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 starts = lines[0].split(/\s+/).map(Number);
    const ends = lines[1].split(/\s+/).map(Number);
    const sizes = lines[2].split(/\s+/).map(Number);
    const profits = lines[3].split(/\s+/).map(Number);
    const maxSize = parseInt(lines[4]);

    const n = starts.length;

    // 按结束时间排序
    const jobs = [];
    for (let i = 0; i < n; i++) {
        jobs.push([ends[i], starts[i], sizes[i], profits[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    const endTimes = jobs.map(j => j[0]);

    // 二分查找前驱
    const p = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        const si = jobs[i][1];
        let lo = 0, hi = i - 1, pos = -1;
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (endTimes[mid] <= si) {
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        p[i] = pos;
    }

    // dp[i+1][w] = 前 i+1 条航线、已用容量 w 的最大利润
    const dp = [];
    for (let i = 0; i <= n; i++) {
        dp.push(new Float64Array(maxSize + 1));
    }

    for (let i = 0; i < n; i++) {
        const sz = jobs[i][2];
        const pr = jobs[i][3];
        const pi = p[i];
        for (let w = 0; w <= maxSize; w++) {
            dp[i + 1][w] = dp[i][w];
            if (w >= sz) {
                const take = dp[pi + 1][w - sz] + pr;
                if (take > dp[i + 1][w]) {
                    dp[i + 1][w] = take;
                }
            }
        }
    }

    let ans = 0;
    for (let w = 0; w <= maxSize; w++) {
        if (dp[n][w] > ans) ans = dp[n][w];
    }

    console.log(ans);
});