OI Wiki 区间 DP如何求解区间合并类问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki当你遇到「把若干元素两两合并、每次合并产生收益/代价最终求全局最优」这类题目如石子合并、能量项链时OI-wiki 的 区间 DP 页面给出了完整的建模方法状态设计、转移方程、转移顺序、环的处理以及 四边形不等式 页面给出的 Knuth 优化实现。这篇文章按这条路径把解题操作走一遍最终得到可直接编码的三层结构定义状态 → 按区间长度递推 → 环上问题取最优起点。先判断题目是否符合区间合并模型区间 DP 给出的三个特征满足它们才能用这套做法合并将两个或多个部分进行整合也可以反过来拆特征能将问题分解为能两两合并的形式求解对整个问题设最优值枚举合并点将问题分解为左右两个部分最后合并两个部分的最优值得到原问题的最优值。典型例题是「NOI1995 石子合并」环上有 $n$ 堆石子每次把相邻两堆合并成一堆得分为新堆石子数之和求最大化得分。若题目是线性结构链上按下面的方法求解若是环见专门一节。定义状态与转移方程文档以链上的石子合并为例。令 $f(i,j)$ 表示将区间 $[i,j]$ 内的所有石子合并到一起的最大得分状态转移方程为$$f(i,j)\max{f(i,k)f(k1,j)\sum_{ti}^{j} a_t }~(i\le kj)$$其中 $a_t$ 是第 $t$ 堆石子的数量。为把 $O(n)$ 的求和降到 $O(1)$令 $sum_i$ 为 $a$ 数组的前缀和方程变形为$$f(i,j)\max{f(i,k)f(k1,j)sum_j-sum_{i-1} }$$这就是区间合并类问题的标准形态状态是区间端点 $(i,j)$决策是合并点 $k$合并代价只依赖区间端点。确定转移顺序以区间长度为阶段计算 $f(i,j)$ 时需要所有 $f(i,k)$ 和 $f(k1,j)$而这些子状态包含的元素数量都少于 $f(i,j)$。因此文档给出的转移顺序是以 $len j-i1$ 作为 DP 的阶段从小到大枚举 $len$从 2 开始枚举左端点 $i$由 $j len i - 1$ 算出右端点枚举合并点 $k$在 $[i, j-1]$ 范围内更新 $f(i,j)$。该做法的时间复杂度为 $O(n^3)$。实现下面是文档 区间 DP 中的实现。其中n为元素个数sum为前缀和数组f为二维状态数组按max原地更新需预先清零链上版本把循环上界2 * n - len改回n - len即可因为链上不存在延长的第二份数据。 Cfor (len 2; len n; len) for (i 1; i 2 * n - len; i) { int j len i - 1; for (k i; k j; k) f[i][j] max(f[i][j], f[i][k] f[k 1][j] sum[j] - sum[i - 1]); } Pythonfor len in range(2, n 1): for i in range(1, 2 * n - len 1): j len i - 1 for k in range(i, j): f[i][j] max(f[i][j], f[i][k] f[k 1][j] sum[j] - sum[i - 1])注意这段代码本身已按环的规模$2n$ 堆编写即下文方法二。链上问题只需把区间长度限制在 $n$ 以内。处理环两种方法题目中石子围成环时文档给出两种处理方式方法一枚举分开的位置将环转化为链。需要枚举 $n$ 次总时间复杂度 $O(n^4)$仅在 $n$ 较小时可行。方法二推荐将链延长两倍变成 $2n$ 堆其中第 $i$ 堆与第 $ni$ 堆相同。用上面的 DP 求解后答案取 $f(1,n), f(2,n1), \dots, f(n,2n-1)$ 中的最优值。时间复杂度 $O(n^3)$。也就是说环上问题不需要改状态定义只需把枚举区间扩到 $2n$最后在 $n$ 个起点中取最大值作为答案。用 Knuth 优化把复杂度降到 O(n²)当 $n$ 大到 $O(n^3)$ 过不了时四边形不等式 页面的「区间合并问题」一节给出优化条件。状态转移方程写作$$f(j,i) \min_{j \leq k i} f(j,k) f(k1,i) w(j,i) \qquad (1\le j i\le n)$$其中 $f(i,i)0$$w(j,i)$ 是合并 $[j,i]$ 的代价。若成本函数 $w$ 同时满足区间包含单调性任意 $a \leq b \leq c \leq d$ 时 $w(b,c) \leq w(a,d)$和四边形不等式$w(a,c)w(b,d) \leq w(a,d)w(b,c)$则最小最优决策 $\operatorname{opt}(j,i)$ 满足$$\operatorname{opt}(j,i-1) \leq \operatorname{opt}(j,i) \leq \operatorname{opt}(j1,i)$$因此枚举 $k$ 时不必扫全区间只需在 $\operatorname{opt}(j,i-1)$ 到 $\operatorname{opt}(j1,i)$ 之间搜索整体复杂度从 $O(n^3)$ 降到 $O(n^2)$。该算法即 Knuth 优化Knuth-Yao speedup。文档给出的参考实现位于 quadrangle-knuth-optimization.cpp核心部分如下w(j,i)为需自行实现的合并代价函数f为最优值opt记录最小最优决策val_t w(int j, int i); // 成本函数 val_t f[N][N]; // 最优值 int opt[N][N]; // 最小最优决策 // 求解整个区间 [1,n] 对应的问题 void solve(int n) { // 初始化 for (int i 1; i n; i) { f[i][i] 0; opt[i][i] i; } // 枚举区间长度 for (int len 2; len n; len) { // 枚举长度为 len 的所有区间 for (int j 1, i len; i n; j, i) { f[j][i] inf; for (int k opt[j][i - 1]; k opt[j 1][i]; k) if (f[j][i] f[j][k] f[k 1][i] w(j, i)) { f[j][i] f[j][k] f[k 1][i] w(j, i); // 更新状态值 opt[j][i] k; // 更新最小最优决策点 } } } }使用前需确认两点一是 $w$ 满足上述两个条件文档「满足四边形不等式的函数类」一节给出了若干可直接引用的判定性质二是注意此实现求的是最小代价版本若原题求最大值如石子合并得分需按同样的opt区间限制自行调整比较方向。结果验证与练习验证是否做对按文档给出的指标检查链上 $n$ 堆的暴力递推应为 $O(n^3)$环上方法二同样 $O(n^3)$方法一是 $O(n^4)$环上答案必须来自 $f(1,n), f(2,n1), \dots, f(n,2n-1)$ 这 $n$ 个值的最优值而不是直接取 $f(1,2n)$使用 Knuth 优化后k的枚举范围应被限制在 $[\operatorname{opt}(j,i-1), \operatorname{opt}(j1,i)]$ 内复杂度降为 $O(n^2)$。文档给出的练习NOIP 2006 能量项链、NOIP 2007 矩阵取数游戏、「IOI2000」邮局。其中「IOI2000」邮局属于区间分拆而非区间合并但它与区间合并共享同一套四边形不等式优化框架可作为对照题练习。进一步阅读可回到 区间 DP 与 四边形不等式 两个页面后者还包含分治、二分队列、简化 LARSCH 等针对区间分拆问题的 $O(n\log n)$ 算法供处理合并类之外的区间问题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI Wiki 区间 DP：如何求解区间合并类问题
OI Wiki 区间 DP如何求解区间合并类问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki当你遇到「把若干元素两两合并、每次合并产生收益/代价最终求全局最优」这类题目如石子合并、能量项链时OI-wiki 的 区间 DP 页面给出了完整的建模方法状态设计、转移方程、转移顺序、环的处理以及 四边形不等式 页面给出的 Knuth 优化实现。这篇文章按这条路径把解题操作走一遍最终得到可直接编码的三层结构定义状态 → 按区间长度递推 → 环上问题取最优起点。先判断题目是否符合区间合并模型区间 DP 给出的三个特征满足它们才能用这套做法合并将两个或多个部分进行整合也可以反过来拆特征能将问题分解为能两两合并的形式求解对整个问题设最优值枚举合并点将问题分解为左右两个部分最后合并两个部分的最优值得到原问题的最优值。典型例题是「NOI1995 石子合并」环上有 $n$ 堆石子每次把相邻两堆合并成一堆得分为新堆石子数之和求最大化得分。若题目是线性结构链上按下面的方法求解若是环见专门一节。定义状态与转移方程文档以链上的石子合并为例。令 $f(i,j)$ 表示将区间 $[i,j]$ 内的所有石子合并到一起的最大得分状态转移方程为$$f(i,j)\max{f(i,k)f(k1,j)\sum_{ti}^{j} a_t }~(i\le kj)$$其中 $a_t$ 是第 $t$ 堆石子的数量。为把 $O(n)$ 的求和降到 $O(1)$令 $sum_i$ 为 $a$ 数组的前缀和方程变形为$$f(i,j)\max{f(i,k)f(k1,j)sum_j-sum_{i-1} }$$这就是区间合并类问题的标准形态状态是区间端点 $(i,j)$决策是合并点 $k$合并代价只依赖区间端点。确定转移顺序以区间长度为阶段计算 $f(i,j)$ 时需要所有 $f(i,k)$ 和 $f(k1,j)$而这些子状态包含的元素数量都少于 $f(i,j)$。因此文档给出的转移顺序是以 $len j-i1$ 作为 DP 的阶段从小到大枚举 $len$从 2 开始枚举左端点 $i$由 $j len i - 1$ 算出右端点枚举合并点 $k$在 $[i, j-1]$ 范围内更新 $f(i,j)$。该做法的时间复杂度为 $O(n^3)$。实现下面是文档 区间 DP 中的实现。其中n为元素个数sum为前缀和数组f为二维状态数组按max原地更新需预先清零链上版本把循环上界2 * n - len改回n - len即可因为链上不存在延长的第二份数据。 Cfor (len 2; len n; len) for (i 1; i 2 * n - len; i) { int j len i - 1; for (k i; k j; k) f[i][j] max(f[i][j], f[i][k] f[k 1][j] sum[j] - sum[i - 1]); } Pythonfor len in range(2, n 1): for i in range(1, 2 * n - len 1): j len i - 1 for k in range(i, j): f[i][j] max(f[i][j], f[i][k] f[k 1][j] sum[j] - sum[i - 1])注意这段代码本身已按环的规模$2n$ 堆编写即下文方法二。链上问题只需把区间长度限制在 $n$ 以内。处理环两种方法题目中石子围成环时文档给出两种处理方式方法一枚举分开的位置将环转化为链。需要枚举 $n$ 次总时间复杂度 $O(n^4)$仅在 $n$ 较小时可行。方法二推荐将链延长两倍变成 $2n$ 堆其中第 $i$ 堆与第 $ni$ 堆相同。用上面的 DP 求解后答案取 $f(1,n), f(2,n1), \dots, f(n,2n-1)$ 中的最优值。时间复杂度 $O(n^3)$。也就是说环上问题不需要改状态定义只需把枚举区间扩到 $2n$最后在 $n$ 个起点中取最大值作为答案。用 Knuth 优化把复杂度降到 O(n²)当 $n$ 大到 $O(n^3)$ 过不了时四边形不等式 页面的「区间合并问题」一节给出优化条件。状态转移方程写作$$f(j,i) \min_{j \leq k i} f(j,k) f(k1,i) w(j,i) \qquad (1\le j i\le n)$$其中 $f(i,i)0$$w(j,i)$ 是合并 $[j,i]$ 的代价。若成本函数 $w$ 同时满足区间包含单调性任意 $a \leq b \leq c \leq d$ 时 $w(b,c) \leq w(a,d)$和四边形不等式$w(a,c)w(b,d) \leq w(a,d)w(b,c)$则最小最优决策 $\operatorname{opt}(j,i)$ 满足$$\operatorname{opt}(j,i-1) \leq \operatorname{opt}(j,i) \leq \operatorname{opt}(j1,i)$$因此枚举 $k$ 时不必扫全区间只需在 $\operatorname{opt}(j,i-1)$ 到 $\operatorname{opt}(j1,i)$ 之间搜索整体复杂度从 $O(n^3)$ 降到 $O(n^2)$。该算法即 Knuth 优化Knuth-Yao speedup。文档给出的参考实现位于 quadrangle-knuth-optimization.cpp核心部分如下w(j,i)为需自行实现的合并代价函数f为最优值opt记录最小最优决策val_t w(int j, int i); // 成本函数 val_t f[N][N]; // 最优值 int opt[N][N]; // 最小最优决策 // 求解整个区间 [1,n] 对应的问题 void solve(int n) { // 初始化 for (int i 1; i n; i) { f[i][i] 0; opt[i][i] i; } // 枚举区间长度 for (int len 2; len n; len) { // 枚举长度为 len 的所有区间 for (int j 1, i len; i n; j, i) { f[j][i] inf; for (int k opt[j][i - 1]; k opt[j 1][i]; k) if (f[j][i] f[j][k] f[k 1][i] w(j, i)) { f[j][i] f[j][k] f[k 1][i] w(j, i); // 更新状态值 opt[j][i] k; // 更新最小最优决策点 } } } }使用前需确认两点一是 $w$ 满足上述两个条件文档「满足四边形不等式的函数类」一节给出了若干可直接引用的判定性质二是注意此实现求的是最小代价版本若原题求最大值如石子合并得分需按同样的opt区间限制自行调整比较方向。结果验证与练习验证是否做对按文档给出的指标检查链上 $n$ 堆的暴力递推应为 $O(n^3)$环上方法二同样 $O(n^3)$方法一是 $O(n^4)$环上答案必须来自 $f(1,n), f(2,n1), \dots, f(n,2n-1)$ 这 $n$ 个值的最优值而不是直接取 $f(1,2n)$使用 Knuth 优化后k的枚举范围应被限制在 $[\operatorname{opt}(j,i-1), \operatorname{opt}(j1,i)]$ 内复杂度降为 $O(n^2)$。文档给出的练习NOIP 2006 能量项链、NOIP 2007 矩阵取数游戏、「IOI2000」邮局。其中「IOI2000」邮局属于区间分拆而非区间合并但它与区间合并共享同一套四边形不等式优化框架可作为对照题练习。进一步阅读可回到 区间 DP 与 四边形不等式 两个页面后者还包含分治、二分队列、简化 LARSCH 等针对区间分拆问题的 $O(n\log n)$ 算法供处理合并类之外的区间问题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考