题解：AcWing 6023 合并石子

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6023. 合并石子 - AcWing题库【题目描述】在一个操场上一排地摆放着N NN堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 22堆石子合并成新的一堆并将新的一堆石子数记为该次合并的得分。计算出将N NN堆石子合并成一堆的最小得分。【输入】第一行为一个正整数N NN。以下N NN行每行一个正整数分别表示第i ii堆石子的个数。【输出】一个正整数即最小得分。【输入样例】7 13 7 8 16 21 4 18【输出样例】239【解题思路】【算法标签】#区间DP#【代码详解】// 引入所有标准库头文件方便使用各种标准库功能#includebits/stdc.h// 使用标准命名空间避免每次使用标准库函数时都需要加 std:: 前缀usingnamespacestd;// 定义常量constintN310;// 定义数组的最大尺寸为310以适应输入数据的需求constintINF1e9;// 定义一个很大的数表示无穷大用于初始化最小值// 定义全局变量intn;// n: 输入的元素数量ints[N];// s[N]: 前缀和数组用于存储前i个元素的和intf[N][N];// f[i][j]: 表示将区间[i, j]合并所需的最小代价// 主函数程序的入口点intmain(){// 读取输入的元素数量 ncinn;// 循环读取每个元素的值并计算前缀和数组 s[i]for(inti1;in;i){// 读取第i个元素的值cins[i];// 计算前缀和s[i] s[i-1] 当前元素的值s[i]s[i-1];// 前缀和}// // 动态规划部分计算将各个区间合并所需的最小代价// // 外层循环遍历所有可能的区间长度 len从2到nfor(intlen2;lenn;len){// 中层循环遍历所有可能的起始位置 i确保区间[i, j]在有效范围内for(inti1;in-len1;i){// 计算区间的结束位置 jintjilen-1;// 初始化将区间[i, j]合并的最小代价为无穷大f[i][j]INF;// 内层循环遍历所有可能的分割点 k将区间[i, j]分割为[i, k]和[k1, j]for(intki;kj;k){// 更新将区间[i, j]合并的最小代价为当前最小代价和分割后两部分代价之和加上区间和的最小值f[i][j]min(f[i][j],f[i][k]f[k1][j]s[j]-s[i-1]);}}}// // 输出结果将整个区间[1, n]合并所需的最小代价// // 输出将整个区间[1, n]合并所需的最小代价 f[1][n]coutf[1][n]endl;// 程序正常结束返回 0return0;}【运行结果】7 13 7 8 16 21 4 18 239