当前位置：首页 > news >正文

题解：AcWing 6023 合并石子

news 2026/5/2 10:24:04

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6023. 合并石子 - AcWing题库

【题目描述】

在一个操场上一排地摆放着N NN堆石子。

现要将石子有次序地合并成一堆。

规定每次只能选相邻的2 22堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将N NN堆石子合并成一堆的最小得分。

【输入】

第一行为一个正整数N NN。

以下N NN行，每行一个正整数，分别表示第i ii堆石子的个数。

【输出】

一个正整数，即最小得分。

【输入样例】

7 13 7 8 16 21 4 18

【输出样例】

【解题思路】

【算法标签】

#区间DP#

【代码详解】

// 引入所有标准库头文件，方便使用各种标准库功能#include<bits/stdc++.h>// 使用标准命名空间，避免每次使用标准库函数时都需要加 std:: 前缀usingnamespacestd;// 定义常量constintN=310;// 定义数组的最大尺寸为310，以适应输入数据的需求constintINF=1e9;// 定义一个很大的数，表示无穷大，用于初始化最小值// 定义全局变量intn;// n: 输入的元素数量ints[N];// s[N]: 前缀和数组，用于存储前i个元素的和intf[N][N];// f[i][j]: 表示将区间[i, j]合并所需的最小代价// 主函数，程序的入口点intmain(){// 读取输入的元素数量 ncin>>n;// 循环读取每个元素的值，并计算前缀和数组 s[i]for(inti=1;i<=n;i++){// 读取第i个元素的值cin>>s[i];// 计算前缀和：s[i] = s[i-1] + 当前元素的值s[i]+=s[i-1];// 前缀和}// =============================// 动态规划部分：计算将各个区间合并所需的最小代价// =============================// 外层循环：遍历所有可能的区间长度 len，从2到nfor(intlen=2;len<=n;len++){// 中层循环：遍历所有可能的起始位置 i，确保区间[i, j]在有效范围内for(inti=1;i<=n-len+1;i++){// 计算区间的结束位置 jintj=i+len-1;// 初始化将区间[i, j]合并的最小代价为无穷大f[i][j]=INF;// 内层循环：遍历所有可能的分割点 k，将区间[i, j]分割为[i, k]和[k+1, j]for(intk=i;k<j;k++){// 更新将区间[i, j]合并的最小代价为当前最小代价和分割后两部分代价之和加上区间和的最小值f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);}}}// =============================// 输出结果：将整个区间[1, n]合并所需的最小代价// =============================// 输出将整个区间[1, n]合并所需的最小代价 f[1][n]cout<<f[1][n]<<endl;// 程序正常结束，返回 0return0;}