信奥赛CSP-J复赛集训DP专题33石子合并题目描述设有N ( N ≤ 300 ) N(N \le 300)N(N≤300)堆石子排成一排其编号为1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N1,2,3,⋯,N。每堆石子有一定的质量m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000)mi​(mi​≤1000)。现在要将这N NN堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同合并的总代价也不相同。试找出一种合理的方法使总的代价最小并输出最小代价。输入格式第一行一个整数N NN。第二行N NN个整数m i m_imi​。输出格式输出文件仅一个整数也就是最小代价。输入输出样例 #1输入 #14 2 5 3 1输出 #122AC代码#includebits/stdc.husingnamespacestd;intn,a[310],sum[310];// a[]存储每堆石子质量sum[]为前缀和数组intdp[310][310];// dp[i][j]表示合并区间[i,j]的最小代价intmain(){cinn;// 读取数据并计算前缀和for(inti1;in;i){cina[i];sum[i]sum[i-1]a[i];// sum[i]表示前i堆石子的总质量}// 初始化DP数组为无穷大表示未计算状态memset(dp,0x3f,sizeof(dp));// 单个石子堆无需合并代价为0for(inti1;in;i){dp[i][i]0;}// 区间DP核心算法for(intlen2;lenn;len){// 枚举区间长度for(inti1;ilen-1n;i){// 枚举区间起点intjilen-1;// 计算区间终点for(intki;kj;k){// 枚举分割点// 状态转移方程合并[i,k]和[k1,j]的代价 当前合并的总质量dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]);}}}coutdp[1][n]endl;// 输出合并全部石子的最小代价return0;}功能分析1. 问题建模目标将N堆相邻石子合并为一堆要求合并总代价最小限制每次只能合并相邻两堆合并代价为两堆质量之和输入石子数量n每堆石子质量数组a[]输出最小合并代价2. 核心算法区间动态规划状态定义dp[i][j]表示合并第i堆到第j堆石子的最小代价边界条件当ij时单堆石子dp[i][i] 0状态转移dp[i][j]min{dp[i][k]dp[k1][j]}sum(i,j)(i ≤ kj)其中sum(i,j)表示区间[i,j]石子总质量通过前缀和数组O(1)计算3. 前缀和优化sum数组预处理前缀和数组sum[i] a[1]a[2]...a[i]快速计算区间和sum[j] - sum[i-1]可快速得到区间[i,j]的总质量4. 算法流程预处理前缀和数组初始化DP边界条件枚举区间长度从2到n枚举区间起点枚举区间分割点根据状态转移方程更新DP表5. 复杂度分析时间复杂度O(n³) → 三重循环n≤300时可接受空间复杂度O(n²) → DP表存储文末福利csp信奥赛复赛12大高频考点专题集训助力你冲刺csp一等奖课程直通链接https://edu.csdn.net/course/detail/40437csp信奥赛复赛集训课涵盖12大高频考点专题集训内容1、语法基础专题2、数学思维专题3、模拟算法专题4、排序算法专题5、贪心算法专题6、二分算法专题7、前缀和差分8、深度优先搜索9、广度优先搜索10、动态规划专题11、栈和队列专题12、树和图专题