题目链接P1880 [NOI1995] 石子合并 - 洛谷区间 DP 相比于其他类型的动态规划 DP 比较简单一点因为理解起来难度不算大而且相对来说我认为这个用法不算特别灵活。只要事先理解了区间 DP 的模板实际做起题还是很好做的。我先以最经典的区间 DP 模板题目说一下实现细节再详细说如何识别题目要用区间 DP 的意图。在这题描述很简单也很好理解读完题目能让人困惑的也许也就只有两点1. 这个石子是摆成环形的那我找最优合并方法还怎么分辨方向 2. 怎么才能找到最优的合并顺序使得得分最大和最小呢首先是处理环形问题只要见到环形的基本都是直接把它原本的数复制一次放在后面利用类似链状的方式来做题也就是化环为链。比如一个数组 arr 元素 2659 组成一个环状。对此我们可以存储数组的时候直接复制一份接在后面看看是什么样的效果。原本我们存储的也就是下标 1-4 的 2659 。这不足以表达出环状。而我们复制一份到后面接上后可以发现下标 2-5 是 6592 3-6 是 5926 4-7 是 9265 。因为我们在环上是没有一个固定的起点的任何一个点都可以作为一个起点。所以要变成链状就只能向上面一样复制一份一样的放在后面接上那么就可以完美模拟好我们的环状了。这样做之后在接下来的区间 DP 我们就不用纠结应该从那个作为起点了要注意的是我们虽然数组长度变成了 2n 可是我们接下来的枚举的区间长度最长的肯定还是 n 。接下来我们需要考虑怎么找到这个最优的合并方法了。我们先理清楚它的合并规则规定每次必须只能合并相邻的两堆且合并后的得分是两堆的石子数的总质量。当我们看到有这种题目有“区间”“相邻合并”的类似意思的字眼且还是那种求方案数最优值等等还不要求记录合并过程只要结果几乎就可以确定就是区间 DP 了。我们首先要定义一个 dp 数组dp[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最优分数。因为这题需要我们求最大和最小都要求出来所以我以dpmax[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最大分数dpmin[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最小分数。然后推导状态转移方程。我们要聚焦的重点是“相邻”由于它限制了只能合并相邻的两堆石子所以可以知道想要把 [i,j] 区间所有石子堆合并成一个那必然是由 [i,k] 和 [k1,j] 这两堆k是区间 [i,j] 内任意一个石子堆下标已经合并好的石子合并而成的。如图示至于要取得哪一个 k 位置来合并成 [i,j] 我们就遍历一次 [i,j] 来比较即可。而根据我们的合成规则我们需要快速得知区间 [i,k] 和 [k1,j] 分别的和所以我们在进行 dp 之前需要对原数组进行一次前缀和预处理。我先定义我的前缀和数组为 sum 。可以发现我们将 [i,k] 和 [k1,j] 合并而我们也能根据我们的 dp 定义直接拿到 [i,k] 和 [k1,j] 的合并成一堆的得分即 dp[i][k] 和 dp[k1][j] 那这样加上它们合并产生的新得分就是 dp[i][j] 了。所以最后我们推导出来的状态转移方程就是dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]) (ikj)dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]) (ikj)推导出状态转移方程我们还需要考虑一点就是我们该如何写循环进行 dp了。先给出正确的代码给大家参考再逐一解释。//最外层枚举区间长度len for(int len2;lenn;len){ //第二层枚举左端点i for(int i1;ilen-12*n;i){ int jilen-1;//区间长度为len左端点为i可直接算出右端点 //得知左右端点后枚举k的位置注意k不能等于j否则k1会大于j for(int ki;kj;k){ dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]); dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]); } } }我们观察我们的 dp 状态转移方程能发现我们的区间 [i,j] 是由小区间 [i,k] 和 [k1,j] 推导而得的。所以如果我要计算一个大区间的得分那我肯定要知道比它小的所有区间的得分否则我们很容易就会用没被计算好的 dp 值进行计算导致结果出错。所以我们最外层的 for 循环应该从小到大枚举区间长度 len 且要注意 len 最大一定是 n。即保证算一个区间长度的所有情况时比它小的区间长度情况肯定已经算好了保证不会出现计算错误用没有算过的地方。第二层当然是枚举左端点 i 枚举 i 还可以直接利用区间长度算出右端点 j 了。要注意的是枚举的区间 [i,j] 不能大于 2n 否则就超过范围了。这时得知了左端点 i 和右端点 j 我们就可以直接枚举 k 了按状态转移方程取得最优值。最后要注意的是初始化问题。区间长度为 1 本身就不需要合并自成一堆所以只用把所有的 dp[i][i] 初始化为 0 就好了。而且我们进行完 dp 循环后我们还要找到环形的最优答案也就是分别以 1-n 每个作为链的起点来合并的方案哪个最优。最终代码如下。#include bits/stdc.h using namespace std; int dpmin[210][210]; int dpmax[210][210]; int n; int sum[210]; int arr[210]; int main(){ cinn; for(int i1;in;i){ cinarr[i]; sum[i]sum[i-1]arr[i]; } //将环变成链状 for(int in1;i2*n;i){ sum[i]sum[i-1]arr[i-n]; } memset(dpmin,0x3f,sizeof(dpmin)); memset(dpmax,0xc0,sizeof(dpmax)); for(int i1;i2*n;i) dpmin[i][i]dpmax[i][i]0;//初始化 //区间dp主循环 for(int len2;lenn;len){ for(int i1;ilen-12*n;i){ int jilen-1; for(int ki;kj;k){ dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]); dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]); } } } //找最大值和最小值 int tmin1e9,tmax-1e9; for(int i1;in;i){ tminmin(tmin,dpmin[i][in-1]); tmaxmax(tmax,dpmax[i][in-1]); } couttmin\ntmax; }其实基本上大部分的区间 dp 都是类似这样的模板都是先枚举区间长度后枚举左端点然后算出右端点最后枚举从哪个地方作为合并。所以区间 dp 的题目基本都是时间复杂度会来到 O($n^3$) 可以看到这个题目的数据量也是只有 100 而已。所以也可以确定出一道题如果有出现“相邻合并”之类的意思而且数据量还能够满足 O($n^3$) 也就是 100 左右基本上都是完全可以考虑用区间 dp 了。
【动态规划】区间 DP ：三层循环逻辑与模板实现细节（洛谷 P1880）
发布时间：2026/7/6 13:42:26
题目链接P1880 [NOI1995] 石子合并 - 洛谷区间 DP 相比于其他类型的动态规划 DP 比较简单一点因为理解起来难度不算大而且相对来说我认为这个用法不算特别灵活。只要事先理解了区间 DP 的模板实际做起题还是很好做的。我先以最经典的区间 DP 模板题目说一下实现细节再详细说如何识别题目要用区间 DP 的意图。在这题描述很简单也很好理解读完题目能让人困惑的也许也就只有两点1. 这个石子是摆成环形的那我找最优合并方法还怎么分辨方向 2. 怎么才能找到最优的合并顺序使得得分最大和最小呢首先是处理环形问题只要见到环形的基本都是直接把它原本的数复制一次放在后面利用类似链状的方式来做题也就是化环为链。比如一个数组 arr 元素 2659 组成一个环状。对此我们可以存储数组的时候直接复制一份接在后面看看是什么样的效果。原本我们存储的也就是下标 1-4 的 2659 。这不足以表达出环状。而我们复制一份到后面接上后可以发现下标 2-5 是 6592 3-6 是 5926 4-7 是 9265 。因为我们在环上是没有一个固定的起点的任何一个点都可以作为一个起点。所以要变成链状就只能向上面一样复制一份一样的放在后面接上那么就可以完美模拟好我们的环状了。这样做之后在接下来的区间 DP 我们就不用纠结应该从那个作为起点了要注意的是我们虽然数组长度变成了 2n 可是我们接下来的枚举的区间长度最长的肯定还是 n 。接下来我们需要考虑怎么找到这个最优的合并方法了。我们先理清楚它的合并规则规定每次必须只能合并相邻的两堆且合并后的得分是两堆的石子数的总质量。当我们看到有这种题目有“区间”“相邻合并”的类似意思的字眼且还是那种求方案数最优值等等还不要求记录合并过程只要结果几乎就可以确定就是区间 DP 了。我们首先要定义一个 dp 数组dp[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最优分数。因为这题需要我们求最大和最小都要求出来所以我以dpmax[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最大分数dpmin[i][j] 代表合并区间 [i,j] 中所有石头为一堆所获得的最小分数。然后推导状态转移方程。我们要聚焦的重点是“相邻”由于它限制了只能合并相邻的两堆石子所以可以知道想要把 [i,j] 区间所有石子堆合并成一个那必然是由 [i,k] 和 [k1,j] 这两堆k是区间 [i,j] 内任意一个石子堆下标已经合并好的石子合并而成的。如图示至于要取得哪一个 k 位置来合并成 [i,j] 我们就遍历一次 [i,j] 来比较即可。而根据我们的合成规则我们需要快速得知区间 [i,k] 和 [k1,j] 分别的和所以我们在进行 dp 之前需要对原数组进行一次前缀和预处理。我先定义我的前缀和数组为 sum 。可以发现我们将 [i,k] 和 [k1,j] 合并而我们也能根据我们的 dp 定义直接拿到 [i,k] 和 [k1,j] 的合并成一堆的得分即 dp[i][k] 和 dp[k1][j] 那这样加上它们合并产生的新得分就是 dp[i][j] 了。所以最后我们推导出来的状态转移方程就是dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]) (ikj)dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]) (ikj)推导出状态转移方程我们还需要考虑一点就是我们该如何写循环进行 dp了。先给出正确的代码给大家参考再逐一解释。//最外层枚举区间长度len for(int len2;lenn;len){ //第二层枚举左端点i for(int i1;ilen-12*n;i){ int jilen-1;//区间长度为len左端点为i可直接算出右端点 //得知左右端点后枚举k的位置注意k不能等于j否则k1会大于j for(int ki;kj;k){ dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]); dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]); } } }我们观察我们的 dp 状态转移方程能发现我们的区间 [i,j] 是由小区间 [i,k] 和 [k1,j] 推导而得的。所以如果我要计算一个大区间的得分那我肯定要知道比它小的所有区间的得分否则我们很容易就会用没被计算好的 dp 值进行计算导致结果出错。所以我们最外层的 for 循环应该从小到大枚举区间长度 len 且要注意 len 最大一定是 n。即保证算一个区间长度的所有情况时比它小的区间长度情况肯定已经算好了保证不会出现计算错误用没有算过的地方。第二层当然是枚举左端点 i 枚举 i 还可以直接利用区间长度算出右端点 j 了。要注意的是枚举的区间 [i,j] 不能大于 2n 否则就超过范围了。这时得知了左端点 i 和右端点 j 我们就可以直接枚举 k 了按状态转移方程取得最优值。最后要注意的是初始化问题。区间长度为 1 本身就不需要合并自成一堆所以只用把所有的 dp[i][i] 初始化为 0 就好了。而且我们进行完 dp 循环后我们还要找到环形的最优答案也就是分别以 1-n 每个作为链的起点来合并的方案哪个最优。最终代码如下。#include bits/stdc.h using namespace std; int dpmin[210][210]; int dpmax[210][210]; int n; int sum[210]; int arr[210]; int main(){ cinn; for(int i1;in;i){ cinarr[i]; sum[i]sum[i-1]arr[i]; } //将环变成链状 for(int in1;i2*n;i){ sum[i]sum[i-1]arr[i-n]; } memset(dpmin,0x3f,sizeof(dpmin)); memset(dpmax,0xc0,sizeof(dpmax)); for(int i1;i2*n;i) dpmin[i][i]dpmax[i][i]0;//初始化 //区间dp主循环 for(int len2;lenn;len){ for(int i1;ilen-12*n;i){ int jilen-1; for(int ki;kj;k){ dpmin[i][j]min(dpmin[i][j],dpmin[i][k]dpmin[k1][j]sum[j]-sum[i-1]); dpmax[i][j]max(dpmax[i][j],dpmax[i][k]dpmax[k1][j]sum[j]-sum[i-1]); } } } //找最大值和最小值 int tmin1e9,tmax-1e9; for(int i1;in;i){ tminmin(tmin,dpmin[i][in-1]); tmaxmax(tmax,dpmax[i][in-1]); } couttmin\ntmax; }其实基本上大部分的区间 dp 都是类似这样的模板都是先枚举区间长度后枚举左端点然后算出右端点最后枚举从哪个地方作为合并。所以区间 dp 的题目基本都是时间复杂度会来到 O($n^3$) 可以看到这个题目的数据量也是只有 100 而已。所以也可以确定出一道题如果有出现“相邻合并”之类的意思而且数据量还能够满足 O($n^3$) 也就是 100 左右基本上都是完全可以考虑用区间 dp 了。
 ：原理、仪器构成、结果示例)
