P1880 [NOI1995] 石子合并 题解复盘模块区间动态规划Interval DP类型区间DP 前缀和 环形DP目标求石子合并的最小总代价和最大总代价。基本信息项目内容题目编号、来源P1880 NOI1995训练层级B知识版块区间DP、前缀和、环形DP解题前・关键信号识别维度分析目标、约束、底层结构每次只能合并相邻两堆石子最终合并成一堆求总代价最小值和最大值。数据规模n≤100O(n³) 可以通过。候选算法和依据每次最后一定是把左右两个区间合并因此使用区间DP。由于是环形需要断环成链。复杂度预判时间复杂度O(n³)空间复杂度O(n²)解题后・外化复盘维度内容状态定义mn[l][r]区间[l,r]合并成一堆的最小总代价。mx[l][r]区间[l,r]合并成一堆的最大总代价。状态转移枚举最后一次切分点kmn[l][r]min(mn[l][k]mn[k1][r]sum(l,r))mx[l][r]max(mx[l][k]mx[k1][r]sum(l,r))遍历顺序按区间长度递增① 枚举区间长度 len② 枚举左端点 l③ 推出右端点 r④ 枚举切分点 k实现结构 / 核心思路① 将数组复制一遍把环变成链。② 求前缀和。③ 区间DP计算所有长度≤n的区间。④ 枚举所有长度为 n 的区间更新答案。错因回溯① 转移时写成了dp[k][r]导致第 k 堆重复计算。正确应为dp[k1][r]。② 忘记复制数组无法处理环。③ 忘记初始化mn[][]INF。边界和易错点1.dp[i][i]0一堆石子不用合并。2. 求最小值初始化 INF。3. 求最大值初始化 0。4. 环必须复制数组。5. 最后答案只统计长度为 n 的区间。下次看到什么信号我应该想到这个方法看到① 求一段区间最优值。② 最后一步可以拆成左右两个区间。③ 每次操作只能发生在区间内部。想到区间DP。为什么要复制数组原数组4 5 9 4复制4 5 9 4 4 5 9 4例如从第二堆开始断开5 9 4 4对应区间 [2,5]因此所有长度为 n 的区间[1,n] [2,n1] ... [n,2n-1]刚好对应所有断环方式。为什么要加 sum(l,r)例如区间4 5 9最后一次一定会变成(4 5) (9)或者(4) (5 9)左右两边已经分别合并完成。最后左右两堆还要再合并一次。最后一次合并后的石子数45918因此最后一次代价就是sum(l,r)所以状态转移必须写成dp[l][k]dp[k1][r]sum(l,r)为什么枚举区间长度因为dp[1][4]依赖dp[1][2] dp[3][4] dp[1][3] dp[2][4]这些都是更短的区间。因此必须长度2 ↓ 长度3 ↓ 长度4 ↓ …… ↓ 长度n模板for(intlen2;lenn;len){for(intl1;llen-12*n;l){intrllen-1;for(intkl;kr;k){}}}AC完整代码#includeiostream#includealgorithmusingnamespacestd;constintN205;constintINF1e9;inta[N];ints[N];intmn[N][N];intmx[N][N];intmain(){intn;cinn;for(inti1;in;i){cina[i];a[in]a[i];}for(inti1;i2*n;i){s[i]s[i-1]a[i];}for(inti1;i2*n;i){for(intj1;j2*n;j){mn[i][j]INF;mx[i][j]0;}mn[i][i]0;mx[i][i]0;}for(intlen2;lenn;len){for(intl1;llen-12*n;l){intrllen-1;for(intkl;kr;k){intsums[r]-s[l-1];mn[l][r]min(mn[l][r],mn[l][k]mn[k1][r]sum);mx[l][r]max(mx[l][r],mx[l][k]mx[k1][r]sum);}}}intansMinINF;intansMax0;for(intl1;ln;l){intrln-1;ansMinmin(ansMin,mn[l][r]);ansMaxmax(ansMax,mx[l][r]);}coutansMinendl;coutansMaxendl;return0;}模型总结模型状态转移路径DPdp[i][j]从相邻位置转移背包DPdp[j]从容量转移LISdp[i]从前面位置转移区间DPdp[l][r]从左右区间转移区间DP统一模板for(len2;lenn;len){for(l1;llen-1n;l){rllen-1;dp[l][r]初始化;for(kl;kr;k){dp[l][r]最优(dp[l][k],dp[k1][r]);}}}记忆看到 ① 求一个区间最优值 ② 最后一步可以拆成左右两部分 ③ 枚举切分位置 ↓ 想到 区间DP 状态 dp[l][r] ↓ 枚举长度 ↓ 枚举左端点 ↓ 枚举切分点 ↓ dp[l][k]dp[k1][r] ↓ 如果最后还需要一次操作 区间贡献如sum(l,r)P3146 248 题解复盘模块动态规划Dynamic Programming类型区间DP目标通过不断合并相邻且相等的数字使最终数字最大。基本信息项目内容题目编号、来源P3146 USACO 2016 Open Gold训练层级普及/提高−知识版块区间DP解题前・关键信号识别维度分析目标、约束、底层结构每次只能合并相邻且相等的数字最后求能够得到的最大数字。数据规模n≤248典型区间DP规模。候选算法和依据一个区间能否合并只与更短的两个子区间有关因此采用区间DP。复杂度预判时间复杂度O(n³)空间复杂度O(n²)解题后・外化复盘维度内容状态定义dp[l][r]表示区间[l,r]如果能够全部合并成一个数字那么这个数字是多少不能合并则为 0。状态转移枚举最后一次合并的位置k。若dp[l][k]dp[k1][r]且都不为0。则dp[l][r]max(dp[l][r],dp[l][k]1)遍历顺序按区间长度从小到大枚举。因为长区间依赖短区间。实现结构 / 核心思路① 初始化所有长度为1的区间。② 枚举区间长度。③ 枚举左端点。④ 枚举分割点。⑤ 判断左右是否能合并且数值相同。错因回溯① 容易误认为和石子合并一样需要前缀和。② 容易忘记判断左右区间是否能够合并即dp!0。边界和易错点1. 初始化dp[i][i]a[i]。2. 左右区间必须都能合并。3. 左右区间最终数字必须相同才能继续合并。下次看到什么信号我应该想到这个方法看到① 连续区间。② 每次只能合并相邻区间。③ 最后一定由左右两个子区间组成。想到区间DP。为什么这样定义状态例如1 1 2区间[1,2]可以1 1 ↓ 2因此dp[1][2]2;如果1 2不能合并。则dp[1][2]0;表示这个区间无法最终变成一个数字。为什么这样转移设[l......k][k1......r]最后一次操作一定是左区间 右区间因此必须左区间已经合并完成 右区间已经合并完成并且最终数字相同例如2 2才能2 2 ↓ 3因此if(dp[l][k]!0dp[l][k]dp[k1][r]){dp[l][r]max(dp[l][r],dp[l][k]1);}为什么按区间长度枚举因为dp[l][r]依赖dp[l][k] dp[k1][r]而这两个区间一定更短。所以必须长度1 ↓ 长度2 ↓ 长度3 ↓ …… ↓ 长度nAC完整代码#includeiostream#includealgorithmusingnamespacestd;inta[255];intdp[255][255];intmain(){intn;cinn;intans0;for(inti1;in;i){cina[i];dp[i][i]a[i];ansmax(ans,a[i]);}for(intlen2;lenn;len){for(intl1;llen-1n;l){intrllen-1;for(intkl;kr;k){if(dp[l][k]!0dp[l][k]dp[k1][r]){dp[l][r]max(dp[l][r],dp[l][k]1);}}ansmax(ans,dp[l][r]);}}coutans;return0;}模型总结模型状态转移石子合并dp[l][r]最小/最大代价min/max sum248dp[l][r]最终数字左右相等时1与石子合并区别石子合并248求总代价求最终数字需要前缀和不需要前缀和左右区间一定能合并左右必须最终数字相同转移sum转移1记忆看到 ① 相邻区间合并 ② 一个区间最终变成一个数字 ③ 左右区间共同决定答案 ↓ 想到 区间DP ↓ dp[l][r] 表示 区间最终能合成的数字 ↓ 枚举分割点 k ↓ 左右相等 ↓ 1
