带权区间图的最小着色成本问题
字数 7534 2025-12-07 02:12:10

带权区间图的最小着色成本问题

一、题目描述

你有一个由 n 个区间组成的列表，每个区间 i 有：

  • 开始时间 start[i]
  • 结束时间 end[i]（保证 end[i] > start[i]）
  • 一个颜色值 color[i]（整数，表示这个区间必须被染成该颜色）
  • 一个权值 weight[i]（正整数，表示这个区间的“重要性”或“权重”）

目标：
将所有区间安排在一组资源上（可以理解为若干条并行的“时间线”），每条时间线上同一时刻只能有一个区间运行，且同一个区间必须完整地在一条时间线上运行。
如果两个区间在时间上重叠，它们必须被分配到不同的资源上。

着色规则：

  1. 每个区间已经有预定的颜色 color[i]，你必须按照这个颜色给它染色。
  2. 在同一条资源（时间线） 上，相邻的区间（即前一个区间的结束时间 ≤ 后一个区间的开始时间，且它们之间没有其他区间插入）如果颜色相同，则可以合并染色，从而减少染色成本。具体来说：
    • 如果将区间 i 单独染色一次，成本 = weight[i]。
    • 如果在同一条时间线上，前一个区间 j 和后一个区间 k 颜色相同，并且 j 的结束时间 ≤ k 的开始时间，那么在染完 j 后可以不额外花费染 k 的颜色（即延续使用同一种颜色），此时 k 的染色成本 = 0。
    • 注意：如果两个区间颜色不同，即使相邻，也必须分别支付 weight[k] 的成本。

你需要安排这些区间到若干资源上，并决定每条资源上区间的顺序，使得总染色成本最小，并返回这个最小成本。

二、问题分析

这个问题可以分解为：

  1. 区间调度与资源分配：本质是区间图的着色（资源分配）问题，但这里的颜色是区间自带的属性，而资源是我们要分配的“机器”。
  2. 成本计算：在一条资源上，区间按结束时间排序安排，如果相邻两个区间颜色相同且不重叠，就可以节省后一个区间的染色成本。

观察：

  • 如果两个区间时间重叠，它们一定在不同的资源上，因此它们之间的颜色是否相同不会影响成本（因为不在同一条时间线）。
  • 如果两个区间不重叠，我们可以选择将它们放在同一资源上（可能节省成本），也可以放在不同资源上（不会节省成本，但可能因为资源安排限制而必须分开）。

那么如何安排才能最小化总成本？
总成本的下界：如果我们不考虑节省，每个区间单独染色，总成本 = 所有 weight[i] 的和。
节省发生在：颜色相同的区间，按时间顺序排在同一个资源上，并且它们之间没有时间重叠。

三、问题转化

如果我们把区间按照开始时间排序（假设区间索引 1~n 已按开始时间升序排好，如果开始时间相同则按结束时间升序）。
定义 dp[i] 表示考虑前 i 个区间，并且第 i 个区间必须被染色（即它可能开启一次新染色，也可能延续之前的颜色）的最小总成本。

但这样定义不够，因为资源安排会影响哪些区间在同一资源上。
一个经典思路：将问题转化为在带权区间图上选择若干条不相交的链（每条链是一个资源上的区间序列），每条链上相邻的区间颜色相同则可节省后者的成本。

更精确的模型：
设总区间集合为 I。
我们想将 I 分成若干链，每个链是区间的一个序列 (a1, a2, ..., ak)，满足：

  1. 链内区间按结束时间不下降排序（即 end[aj] ≤ start[aj+1]，不重叠且可相邻）；
  2. 链内如果相邻区间颜色相同，则后一个区间的染色成本为 0，否则为 weight[aj+1]。

目标：最小化总成本 = 每个链的第一个区间的成本（weight[a1]） + 链内相邻颜色不同时后一个区间的 weight 之和。

四、动态规划状态设计

我们换个思路：
定义 dp[i] 为考虑前 i 个区间（按结束时间排序） 的最小总成本，但这样不方便处理链的延续。

更好的状态定义（区间DP思想）：

  1. 将所有区间按结束时间升序排序，编号 1~n。
  2. 定义 f[i] 表示只考虑前 i 个区间，并且第 i 个区间是新链的起点（即它前面没有和它同链的区间）的最小总成本。
    但这样状态转移困难。

更常见的区间链式DP方法：
定义 dp[i] 表示考虑前 i 个区间的最小总成本，且不规定第 i 个区间是否与后面的区间同链。
转移时，我们枚举以 i 为当前链的最后一个区间，然后找下一个与 i 不重叠且颜色相同的区间 j，尝试将 j 的成本省掉。但这样是 O(n²) 的。

实际上，我们可以建图：

  • 如果区间 i 和区间 j 不重叠（end[i] ≤ start[j]），并且颜色相同，则连接一条边表示 j 可以“接在” i 后面而不增加成本。
  • 这形成一个DAG（按结束时间排序后，只能从前面的区间连向后面的区间）。

问题变成：在DAG上选择若干条路径（链），覆盖所有区间，使得总成本最小，其中每条路径的第一个节点付出 weight，后续节点如果和前一节点颜色相同则付出 0，否则付出 weight。

可以这样 DP：
设 dp[i] 表示以区间 i 为某条链的末尾时的最小总成本（考虑前 i 个区间的安排，且 i 被包含）。
转移：

  1. 区间 i 单独成链：成本 = dp[p] + weight[i]，其中 p 是最大的索引满足 end[p] < start[i]，表示在 i 开始前已安排好的最小成本。
  2. 区间 i 接在某个区间 j 后面（end[j] ≤ start[i] 且 color[j] = color[i]）：成本 = dp[j]（因为 i 不增加成本）。
  3. 区间 i 接在某个区间 j 后面但颜色不同：成本 = dp[j] + weight[i]。

但这样 dp[i] 只记录以 i 结尾的链成本，没有覆盖所有区间，所以我们需要一个全局状态。

更清晰的 DP 设计（类似加权区间调度 + 颜色匹配）：
定义 dp[i] 为安排完前 i 个区间（按结束时间排序）的最小总成本，且不考虑第 i 个区间之后的情况。
对每个区间 i，有两种选择：

  • 让 i 作为链的开始：成本 = dp[prev(i)] + weight[i]，其中 prev(i) 是与 i 不重叠的前一个区间的最大索引。
  • 让 i 作为链的延续：找到某个 j < i，满足 end[j] ≤ start[i] 且 color[j] = color[i]，并且 j 到 i 之间没有其他区间在同一链上（即 j 是 i 的前驱）。此时成本 = dp[j] + (从 j 到 i 之间不能接在 j 后面的区间必须单独开链的成本)。
    但“之间”的区间处理复杂，因为可能有多个区间在时间上和 j 与 i 重叠。

这个 DP 难以直接写，因为“之间”的区间可能被安排到其他链上。

五、简化与关键发现

我们注意到一个重要性质：
如果我们把所有颜色相同的区间按照时间顺序（不重叠）连接起来，就可以节省成本。
因此，问题等价于：
总成本 = 所有区间的 weight 之和 - 节省的总 weight。
节省发生在：对某个颜色 c 的区间，如果我们能在一个资源上安排它们的一个不重叠子序列（按时间顺序），那么除了第一个，后面的都可以省去 weight。

那么最大节省 = 对每种颜色，选出它的一个不重叠子序列（按时间顺序），使得被选的区间数量最多（每个被选的区间可省去 weight，除了第一个不能省）。

但注意：不同颜色的区间可以穿插在同一个资源上吗？可以，但那样颜色交替时不能节省。
因此，资源安排可以自由决定谁和谁在同一个资源上，目标是最小化成本。

实际上这是一个区间调度 + 颜色匹配的 DP：
定义 dp[t] 表示考虑结束时间 ≤ t 的所有区间的最小成本。
按结束时间处理区间，当处理到区间 i (结束时间 e_i) 时：

  • 它可以单独开新资源：成本 = dp[start_i] + weight[i]。
  • 它可以接在某个之前结束的区间 j 后面（end[j] ≤ start[i]）：
    • 如果颜色相同：成本 = dp[end[j]] + 0（因为 i 不付费）？不对，因为 dp[end[j]] 可能包含 j 付费了，接上 i 不多付。但需确保 j 是前一个。

这需要知道最后处理的区间颜色。

所以状态增加一维颜色：dp[t][c] 表示最后一个区间颜色为 c 且结束时间为 t 的最小成本。但 t 是连续值太大，要离散化。

六、离散化与 DP 状态

离散化所有区间的开始和结束时间，得到 2n 个时间点。
定义 dp[i][c] 表示在时间点 i（对应某个离散化后的时间）时，当前最后处理的区间颜色为 c 的最小成本。但 c 可能很多，用 map 存储。

更简单：区间按结束时间排序，设 dp[i] 表示考虑前 i 个区间的最小总成本，且第 i 个区间被染色（付费或免费）。
转移：

  1. i 单独成链：dp[i] = min(dp[i], dp[prev(i)] + weight[i])，其中 prev(i) 是最大的 j 满足 end[j] < start[i]，如果不存在则 0。
  2. i 接在某个 j 后面（颜色相同且不重叠）：dp[i] = min(dp[i], dp[j])，因为 i 免费。
  3. i 接在某个 j 后面但颜色不同：dp[i] = min(dp[i], dp[j] + weight[i])。

其中情况 2 就是节省的关键。

初始化 dp[0] = 0。
答案是 dp[n] 吗？不一定，因为最后一个区间可能不付费（如果它接在前面同色区间后），但 dp[i] 表示前 i 个区间的最小成本，并且第 i 个区间被考虑进去了（无论付费免费）。
我们需要在最后加上“未付费”的区间？不需要，因为 dp[i] 已经包含了前 i 个的所有区间。

七、算法步骤

  1. 将区间按结束时间升序排序，若结束时间相同则按开始时间升序。
  2. 预处理 prev[i]：对每个 i，找到最大的 j 满足 end[j] < start[i]，用二分查找。
  3. 初始化 dp[0] = 0。
  4. 对 i 从 1 到 n：
    • 初始化 dp[i] = dp[prev[i]] + weight[i]（单独成链）。
    • 枚举所有 j < i 且 end[j] ≤ start[i] 且 color[j] = color[i]：
      • dp[i] = min(dp[i], dp[j]) // i 免费
    • 枚举所有 j < i 且 end[j] ≤ start[i] 且 color[j] != color[i]：
      • dp[i] = min(dp[i], dp[j] + weight[i])
  5. 答案为 dp[n]。

复杂度 O(n²)，在 n 较大时需优化。优化方法：对每个颜色维护一个数据结构（如按结束时间排序的列表），在枚举 j 时只检查同颜色的那些区间，并且对同颜色的情况，我们其实只需要找 end[j] ≤ start[i] 中 dp[j] 最小的那个，因为 i 免费，我们希望前面成本最小。
所以可以维护每种颜色在某个结束时间之前的 dp 最小值，用二分找到最后一个 end[j] ≤ start[i] 的 j 对应的最小值。

八、举例说明

假设区间（按结束时间排序后）：
1: [1,3], color=1, weight=5
2: [2,4], color=2, weight=6
3: [3,5], color=1, weight=4
4: [5,7], color=1, weight=3

总 weight 和 = 18。

计算：

  • dp[0]=0
  • i=1: prev=0, dp[1]=0+5=5。同色 j 无。
  • i=2: prev=0（区间1结束3<开始2?不对，start[2]=2，end[1]=3≥2，所以重叠，prev[2]=0），dp[2]=0+6=6。同色 j 无。
  • i=3: start=3, end=5, prev: 找 end[j]<3，只有区间1结束3不小于3，区间2结束4不小于3，所以 prev=0。dp[3]=0+4=4。同色 j：j=1，end[1]=3≤start[3]=3，同色，dp[3]=min(4, dp[1]=5)=4? 不对，应该是 min(4, dp[1]=5)=4，所以不节省，因为区间1和3时间相邻但区间2在中间重叠？检查：区间1[1,3]和区间3[3,5]是相邻的（不重叠，因为3=3），但区间2[2,4]和区间3重叠，所以区间1和3能否在同一资源？可以，只要区间2不在同一资源。dp[3] 如果接在区间1后免费，dp[3]=dp[1]=5? 反而更大，所以不会选。
  • i=4: start=5, end=7, prev: 找 end[j]<5，j=3 结束5不小于5，j=2结束4<5，所以 prev=2。dp[4]=dp[2]+3=6+3=9。同色 j：j=3（end=5≤5，同色），dp[4]=min(9, dp[3]=4)=4。
    再检查 j=1（end=3≤5，同色），dp[4]=min(4, dp[1]=5)=4。
    所以 dp[4]=4。

总成本=4，但区间2和区间1都付费了吗？ dp[4] 只表示前4个区间的最小成本，但区间2（重6）似乎没算进去？这说明我们的状态设计可能漏了某些区间。

问题出在：dp[i] 只表示“考虑前 i 个区间”，但 i 不一定付费，可能免费，但免费时前面的区间必须覆盖所有之前的区间。我们枚举的转移可能跳过一些区间。我们需要确保所有区间都被安排。

实际上，更可靠的 DP 是：dp[i] 表示前 i 个区间都已安排的最小成本。那么 dp[i] 可以从 dp[prev(i)] 转移而来，再加上某些区间免费。但免费区间必须和前面同色且不重叠。

这变成了在时间线上选择一些区间作为“链起点”，其余尽量免费。

九、标准解法思路（区间图最小路径覆盖变形）

这是一个经典问题：最小化成本 = 总权重 - 最大节省。
最大节省 = 每种颜色内部，选择一些不重叠的边（j→i，color[j]=color[i], end[j]≤start[i]），使得每条边节省 weight[i]，并且每个区间最多作为一个后继、最多作为一个前驱（即形成链），且链上颜色相同。

这等价于：构造二分图，左部右部都是区间，如果 color[i]=color[j] 且 end[i]≤start[j]，则 i→j 连边，权值为 weight[j]。求最大权匹配，匹配的边表示 j 免费。
一个区间只能匹配一个前驱、一个后继。

这就是 DAG 的最小路径覆盖的变种，可以用最大权二分图匹配（KM 或费用流）解决。

为了简单，我们给出 O(n²) DP 解法（假设 n≤2000）：
定义 f[i] 表示以 i 为最后一个免费区间的最大节省值（即 i 免费，且前面可能有一串同色免费区间）。
转移：f[i] = max(weight[i] + max{f[j]})，其中 j 满足：color[j]=color[i], end[j]≤start[i]，并且 j 和 i 之间的其他区间可以安排到其他资源上（这总是可以，因为时间不重叠就可以同资源，重叠就不同资源，不影响）。

初始：f[i] = weight[i]（即 i 单独免费，但免费必须前驱同色，所以不能单独免费，必须 j 存在）。
所以只有存在 j 时才能转移。

最后最大节省 = max{f[i]}。
总成本 = sum(weight) - 最大节省。

验证之前的例子：
sum=18
同色1：区间1,3,4
边：1→3 (省4), 1→4(省3), 3→4(省3)
f[1]=0（不能免费，无前驱）
f[3]=4（从1来）
f[4]=max(3（从1来）, 3+4（从3来? 3→4省3，加上f[3]=4，总省7) 不对，因为3→4省3，加上3免费省的4，总省7，意味着区间3,4都免费，区间1付费5，总成本=5，总省=13? 不对，总省=4+3=7，总成本=18-7=11，但之前dp得到4，矛盾。

这显示我们的模型有误。其实节省不能传递多级？可以传递，只要一条链上颜色全相同。

所以最大节省是找同色的不重叠链，使得链上除第一个外全免费。
那么就是每种颜色内，按时间排序，求最大权不相交区间集？不对，是要让链覆盖尽可能多的区间，但链内必须不重叠且时间顺序。

这其实是每种颜色内，选出一些区间，使得它们不重叠，并且让被选区间数最大（每个被选区间可省 weight，除了第一个不能省）。等等，第一个不能省，所以省的是 weight[后一个]。

重新思考：节省 = 每条链上（颜色相同）的边数，每条边省后一个区间的 weight。
所以要在颜色相同的区间之间连边 j→i（end[j]≤start[i]），边权=weight[i]，求最大权匹配，每个区间入度≤1，出度≤1。

这就是二分图最大权匹配。
左部：所有区间（作为前驱）
右部：所有区间（作为后继）
边：同色且不重叠，权=weight[右]
求最大权匹配，匹配的边数=节省的总权值。

匹配是区间之间的配对，表示后者免费。

然后总成本 = 总weight - 最大匹配权和。

十、算法总结

  1. 输入 n 个区间，按结束时间排序。
  2. 总权重 = sum(weight[i])。
  3. 建二分图，左部 n 个点，右部 n 个点。
    如果 i 和 j 同色且 i 的结束 ≤ j 的开始，则从左 i 到右 j 连边，权值 = weight[j]。
  4. 求最大权匹配（可以用 KM 或费用流）。
  5. 答案 = 总权重 - 最大匹配权值。

复杂度：二分图匹配 O(n^3)，可用费用流 O(n^2 log n) 或 O(n^3) 实现。

这样，我们就得到了带权区间图的最小着色成本的完整解法，从问题理解、转化、建模到算法步骤。

带权区间图的最小着色成本问题 一、题目描述 你有一个由 n 个区间组成的列表，每个区间 i 有： 开始时间 start[i] 结束时间 end[i] （保证 end[i] > start[i] ） 一个颜色值 color[i] （整数，表示这个区间 必须 被染成该颜色） 一个权值 weight[i] （正整数，表示这个区间的“重要性”或“权重”） 目标： 将所有区间安排在一组 资源 上（可以理解为若干条并行的“时间线”），每条时间线上同一时刻只能有一个区间运行，且同一个区间必须完整地在一条时间线上运行。 如果两个区间在时间上重叠，它们必须被分配到不同的资源上。 着色规则 ： 每个区间已经有预定的颜色 color[i] ，你必须按照这个颜色给它染色。 在 同一条资源（时间线） 上，相邻的区间（即前一个区间的结束时间 ≤ 后一个区间的开始时间，且它们之间没有其他区间插入）如果颜色相同，则可以合并染色，从而减少染色成本。具体来说： 如果将区间 i 单独染色一次，成本 = weight[i] 。 如果在同一条时间线上，前一个区间 j 和后一个区间 k 颜色相同，并且 j 的结束时间 ≤ k 的开始时间，那么在染完 j 后可以 不额外花费 染 k 的颜色（即延续使用同一种颜色），此时 k 的染色成本 = 0。 注意：如果两个区间颜色不同，即使相邻，也必须分别支付 weight[k] 的成本。 你需要安排这些区间到若干资源上，并决定每条资源上区间的顺序，使得 总染色成本最小 ，并返回这个最小成本。 二、问题分析 这个问题可以分解为： 区间调度与资源分配 ：本质是区间图的 着色 （资源分配）问题，但这里的颜色是区间自带的属性，而资源是我们要分配的“机器”。 成本计算 ：在一条资源上，区间按结束时间排序安排，如果相邻两个区间颜色相同且不重叠，就可以节省后一个区间的染色成本。 观察： 如果两个区间时间重叠，它们一定在不同的资源上，因此它们之间的颜色是否相同不会影响成本（因为不在同一条时间线）。 如果两个区间不重叠，我们可以选择将它们放在同一资源上（可能节省成本），也可以放在不同资源上（不会节省成本，但可能因为资源安排限制而必须分开）。 那么如何安排才能最小化总成本？ 总成本的下界：如果我们不考虑节省，每个区间单独染色，总成本 = 所有 weight[i] 的和。 节省发生在： 颜色相同的区间，按时间顺序排在同一个资源上，并且它们之间没有时间重叠 。 三、问题转化 如果我们把区间按照 开始时间 排序（假设区间索引 1~n 已按开始时间升序排好，如果开始时间相同则按结束时间升序）。 定义 dp[i] 表示考虑前 i 个区间，并且 第 i 个区间必须被染色 （即它可能开启一次新染色，也可能延续之前的颜色）的最小总成本。 但这样定义不够，因为资源安排会影响哪些区间在同一资源上。 一个经典思路：将问题转化为在 带权区间图 上选择若干条不相交的链（每条链是一个资源上的区间序列），每条链上相邻的区间颜色相同则可节省后者的成本。 更精确的模型： 设总区间集合为 I 。 我们想将 I 分成若干链，每个链是区间的一个序列 (a1, a2, ..., ak) ，满足： 链内区间按结束时间不下降排序（即 end[aj] ≤ start[aj+1] ，不重叠且可相邻）； 链内如果相邻区间颜色相同，则后一个区间的染色成本为 0，否则为 weight[aj+1] 。 目标：最小化总成本 = 每个链的第一个区间的成本（ weight[a1] ） + 链内相邻颜色不同时后一个区间的 weight 之和。 四、动态规划状态设计 我们换个思路： 定义 dp[i] 为 考虑前 i 个区间（按结束时间排序） 的最小总成本，但这样不方便处理链的延续。 更好的状态定义（区间DP思想）： 将所有区间按 结束时间 升序排序，编号 1~n。 定义 f[i] 表示 只考虑前 i 个区间 ，并且 第 i 个区间是新链的起点 （即它前面没有和它同链的区间）的最小总成本。 但这样状态转移困难。 更常见的区间链式DP方法： 定义 dp[i] 表示考虑前 i 个区间的最小总成本，且不规定第 i 个区间是否与后面的区间同链。 转移时，我们枚举以 i 为当前链的最后一个区间，然后找下一个与 i 不重叠且颜色相同的区间 j，尝试将 j 的成本省掉。但这样是 O(n²) 的。 实际上，我们可以建图： 如果区间 i 和区间 j 不重叠（ end[i] ≤ start[j] ），并且颜色相同，则连接一条边表示 j 可以“接在” i 后面而不增加成本。 这形成一个DAG（按结束时间排序后，只能从前面的区间连向后面的区间）。 问题变成：在DAG上选择若干条路径（链），覆盖所有区间，使得总成本最小，其中每条路径的第一个节点付出 weight，后续节点如果和前一节点颜色相同则付出 0，否则付出 weight。 可以这样 DP： 设 dp[i] 表示以区间 i 为某条链的末尾时的最小总成本（考虑前 i 个区间的安排，且 i 被包含）。 转移： 区间 i 单独成链：成本 = dp[ p] + weight[ i]，其中 p 是最大的索引满足 end[p] < start[i] ，表示在 i 开始前已安排好的最小成本。 区间 i 接在某个区间 j 后面（ end[j] ≤ start[i] 且 color[j] = color[i] ）：成本 = dp[ j ]（因为 i 不增加成本）。 区间 i 接在某个区间 j 后面但颜色不同：成本 = dp[ j] + weight[ i ]。 但这样 dp[ i ] 只记录以 i 结尾的链成本，没有覆盖所有区间，所以我们需要一个全局状态。 更清晰的 DP 设计（类似加权区间调度 + 颜色匹配）： 定义 dp[i] 为安排完前 i 个区间（按结束时间排序）的最小总成本，且不考虑第 i 个区间之后的情况。 对每个区间 i，有两种选择： 让 i 作为链的开始：成本 = dp[prev(i)] + weight[i] ，其中 prev(i) 是与 i 不重叠的前一个区间的最大索引。 让 i 作为链的延续：找到某个 j < i，满足 end[j] ≤ start[i] 且 color[j] = color[i] ，并且 j 到 i 之间没有其他区间在同一链上（即 j 是 i 的前驱）。此时成本 = dp[j] + (从 j 到 i 之间不能接在 j 后面的区间必须单独开链的成本) 。 但“之间”的区间处理复杂，因为可能有多个区间在时间上和 j 与 i 重叠。 这个 DP 难以直接写，因为“之间”的区间可能被安排到其他链上。 五、简化与关键发现 我们注意到一个重要性质： 如果我们把 所有颜色相同的区间 按照时间顺序（不重叠）连接起来，就可以节省成本。 因此，问题等价于： 总成本 = 所有区间的 weight 之和 - 节省的总 weight。 节省发生在：对某个颜色 c 的区间，如果我们能在一个资源上安排它们的一个不重叠子序列（按时间顺序），那么除了第一个，后面的都可以省去 weight。 那么最大节省 = 对每种颜色，选出它的一个不重叠子序列（按时间顺序），使得被选的区间数量最多（每个被选的区间可省去 weight，除了第一个不能省）。 但注意：不同颜色的区间可以穿插在同一个资源上吗？可以，但那样颜色交替时不能节省。 因此，资源安排可以自由决定谁和谁在同一个资源上，目标是最小化成本。 实际上这是一个 区间调度 + 颜色匹配 的 DP： 定义 dp[t] 表示考虑结束时间 ≤ t 的所有区间的最小成本。 按结束时间处理区间，当处理到区间 i (结束时间 e_ i) 时： 它可以单独开新资源：成本 = dp[start_i] + weight[i] 。 它可以接在某个之前结束的区间 j 后面（ end[j] ≤ start[i] ）： 如果颜色相同：成本 = dp[end[j]] + 0 （因为 i 不付费）？不对，因为 dp[ end[ j] ] 可能包含 j 付费了，接上 i 不多付。但需确保 j 是前一个。 这需要知道最后处理的区间颜色。 所以状态增加一维颜色： dp[t][c] 表示最后一个区间颜色为 c 且结束时间为 t 的最小成本。但 t 是连续值太大，要离散化。 六、离散化与 DP 状态 离散化所有区间的开始和结束时间，得到 2n 个时间点。 定义 dp[i][c] 表示在时间点 i（对应某个离散化后的时间）时，当前最后处理的区间颜色为 c 的最小成本。但 c 可能很多，用 map 存储。 更简单：区间按结束时间排序，设 dp[i] 表示考虑前 i 个区间的最小总成本，且第 i 个区间被染色（付费或免费）。 转移： i 单独成链： dp[i] = min(dp[i], dp[prev(i)] + weight[i]) ，其中 prev(i) 是最大的 j 满足 end[j] < start[i] ，如果不存在则 0。 i 接在某个 j 后面（颜色相同且不重叠）： dp[i] = min(dp[i], dp[j]) ，因为 i 免费。 i 接在某个 j 后面但颜色不同： dp[i] = min(dp[i], dp[j] + weight[i]) 。 其中情况 2 就是节省的关键。 初始化 dp[0] = 0 。 答案是 dp[n] 吗？不一定，因为最后一个区间可能不付费（如果它接在前面同色区间后），但 dp[ i ] 表示前 i 个区间的最小成本，并且第 i 个区间被考虑进去了（无论付费免费）。 我们需要在最后加上“未付费”的区间？不需要，因为 dp[ i ] 已经包含了前 i 个的所有区间。 七、算法步骤 将区间按结束时间升序排序，若结束时间相同则按开始时间升序。 预处理 prev[i] ：对每个 i，找到最大的 j 满足 end[j] < start[i] ，用二分查找。 初始化 dp[0] = 0 。 对 i 从 1 到 n： 初始化 dp[i] = dp[prev[i]] + weight[i] （单独成链）。 枚举所有 j < i 且 end[j] ≤ start[i] 且 color[j] = color[i] ： dp[i] = min(dp[i], dp[j]) // i 免费 枚举所有 j < i 且 end[j] ≤ start[i] 且 color[j] != color[i] ： dp[i] = min(dp[i], dp[j] + weight[i]) 答案为 dp[n] 。 复杂度 O(n²)，在 n 较大时需优化。优化方法：对每个颜色维护一个数据结构（如按结束时间排序的列表），在枚举 j 时只检查同颜色的那些区间，并且对同颜色的情况，我们其实只需要找 end[j] ≤ start[i] 中 dp[ j ] 最小的那个，因为 i 免费，我们希望前面成本最小。 所以可以维护每种颜色在某个结束时间之前的 dp 最小值，用二分找到最后一个 end[j] ≤ start[i] 的 j 对应的最小值。 八、举例说明 假设区间（按结束时间排序后）： 1: [ 1,3 ], color=1, weight=5 2: [ 2,4 ], color=2, weight=6 3: [ 3,5 ], color=1, weight=4 4: [ 5,7 ], color=1, weight=3 总 weight 和 = 18。 计算： dp[ 0 ]=0 i=1: prev=0, dp[ 1 ]=0+5=5。同色 j 无。 i=2: prev=0（区间1结束3<开始2?不对，start[ 2]=2，end[ 1]=3≥2，所以重叠，prev[ 2]=0），dp[ 2 ]=0+6=6。同色 j 无。 i=3: start=3, end=5, prev: 找 end[ j]<3，只有区间1结束3不小于3，区间2结束4不小于3，所以 prev=0。dp[ 3]=0+4=4。同色 j：j=1，end[ 1]=3≤start[ 3]=3，同色，dp[ 3]=min(4, dp[ 1]=5)=4? 不对，应该是 min(4, dp[ 1]=5)=4，所以不节省，因为区间1和3时间相邻但区间2在中间重叠？检查：区间1[ 1,3]和区间3[ 3,5]是相邻的（不重叠，因为3=3），但区间2[ 2,4]和区间3重叠，所以区间1和3能否在同一资源？可以，只要区间2不在同一资源。dp[ 3] 如果接在区间1后免费，dp[ 3]=dp[ 1 ]=5? 反而更大，所以不会选。 i=4: start=5, end=7, prev: 找 end[ j]<5，j=3 结束5不小于5，j=2结束4<5，所以 prev=2。dp[ 4]=dp[ 2]+3=6+3=9。同色 j：j=3（end=5≤5，同色），dp[ 4]=min(9, dp[ 3 ]=4)=4。 再检查 j=1（end=3≤5，同色），dp[ 4]=min(4, dp[ 1 ]=5)=4。 所以 dp[ 4 ]=4。 总成本=4，但区间2和区间1都付费了吗？ dp[ 4 ] 只表示前4个区间的最小成本，但区间2（重6）似乎没算进去？这说明我们的状态设计可能漏了某些区间。 问题出在：dp[ i ] 只表示“考虑前 i 个区间”，但 i 不一定付费，可能免费，但免费时前面的区间必须覆盖所有之前的区间。我们枚举的转移可能跳过一些区间。我们需要确保所有区间都被安排。 实际上，更可靠的 DP 是： dp[i] 表示前 i 个区间都已安排的最小成本。那么 dp[ i] 可以从 dp[ prev(i) ] 转移而来，再加上某些区间免费。但免费区间必须和前面同色且不重叠。 这变成了在时间线上选择一些区间作为“链起点”，其余尽量免费。 九、标准解法思路（区间图最小路径覆盖变形） 这是一个经典问题：最小化成本 = 总权重 - 最大节省。 最大节省 = 每种颜色内部，选择一些不重叠的边（j→i，color[ j]=color[ i], end[ j]≤start[ i]），使得每条边节省 weight[ i ]，并且每个区间最多作为一个后继、最多作为一个前驱（即形成链），且链上颜色相同。 这等价于：构造二分图，左部右部都是区间，如果 color[ i]=color[ j] 且 end[ i]≤start[ j]，则 i→j 连边，权值为 weight[ j ]。求最大权匹配，匹配的边表示 j 免费。 一个区间只能匹配一个前驱、一个后继。 这就是 DAG 的最小路径覆盖的变种，可以用最大权二分图匹配（KM 或费用流）解决。 为了简单，我们给出 O(n²) DP 解法（假设 n≤2000）： 定义 f[i] 表示以 i 为最后一个免费区间的最大节省值（即 i 免费，且前面可能有一串同色免费区间）。 转移： f[i] = max(weight[i] + max{f[j]}) ，其中 j 满足：color[ j]=color[ i], end[ j]≤start[ i ]，并且 j 和 i 之间的其他区间可以安排到其他资源上（这总是可以，因为时间不重叠就可以同资源，重叠就不同资源，不影响）。 初始： f[i] = weight[i] （即 i 单独免费，但免费必须前驱同色，所以不能单独免费，必须 j 存在）。 所以只有存在 j 时才能转移。 最后最大节省 = max{f[ i ]}。 总成本 = sum(weight) - 最大节省。 验证之前的例子： sum=18 同色1：区间1,3,4 边：1→3 (省4), 1→4(省3), 3→4(省3) f[ 1 ]=0（不能免费，无前驱） f[ 3 ]=4（从1来） f[ 4]=max(3（从1来）, 3+4（从3来? 3→4省3，加上f[ 3 ]=4，总省7) 不对，因为3→4省3，加上3免费省的4，总省7，意味着区间3,4都免费，区间1付费5，总成本=5，总省=13? 不对，总省=4+3=7，总成本=18-7=11，但之前dp得到4，矛盾。 这显示我们的模型有误。其实节省不能传递多级？可以传递，只要一条链上颜色全相同。 所以最大节省是找同色的不重叠链，使得链上除第一个外全免费。 那么就是每种颜色内，按时间排序，求最大权不相交区间集？不对，是要让链覆盖尽可能多的区间，但链内必须不重叠且时间顺序。 这其实是每种颜色内，选出一些区间，使得它们不重叠，并且让被选区间数最大（每个被选区间可省 weight，除了第一个不能省）。等等，第一个不能省，所以省的是 weight[ 后一个 ]。 重新思考：节省 = 每条链上（颜色相同）的边数，每条边省后一个区间的 weight。 所以要在颜色相同的区间之间连边 j→i（end[ j]≤start[ i]），边权=weight[ i ]，求最大权匹配，每个区间入度≤1，出度≤1。 这就是二分图最大权匹配。 左部：所有区间（作为前驱） 右部：所有区间（作为后继） 边：同色且不重叠，权=weight[ 右 ] 求最大权匹配，匹配的边数=节省的总权值。 匹配是区间之间的配对，表示后者免费。 然后总成本 = 总weight - 最大匹配权和。 十、算法总结 输入 n 个区间，按结束时间排序。 总权重 = sum(weight[ i ])。 建二分图，左部 n 个点，右部 n 个点。 如果 i 和 j 同色且 i 的结束 ≤ j 的开始，则从左 i 到右 j 连边，权值 = weight[ j ]。 求最大权匹配（可以用 KM 或费用流）。 答案 = 总权重 - 最大匹配权值。 复杂度：二分图匹配 O(n^3)，可用费用流 O(n^2 log n) 或 O(n^3) 实现。 这样，我们就得到了 带权区间图的最小着色成本 的完整解法，从问题理解、转化、建模到算法步骤。