願

用户名：uq_52564409936

访问量：191

签　名：

等　　级
排　　名	8878
经　　验	1132
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

3060: 合并石子
浏览：102

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

3060: 合并石子

　　作者: 願　　　　发表时间：2023-02-07 13:04:56 浏览：102　|　评论：0　

原题链接：合并石子

## # 合并石子
#### ### 区间dp

------------

##### 解题思路：

------------

f(i,j)表示将从第i堆石子到第j堆石子合并成一堆的最小花费。
思考：特殊情时f(i,j)=?(i=j)
答：f(i,j)=0。
那对于一般情况呢？首先我们先举个栗子QAQ
f(1,4)~f(1,1),f(2,4);
f(1,4)~f(1,2),f(3,4);
f(1,4)~f(1,3),f(4,4);
那么，我们升级到对于任意的f(i,j):

------------

![](/image_editor_upload/20230207/20230207110459_30425.png)

------------

则有以下关系：
#### f(i,j)~min(f(i,j),f(i,k)+f(k+1,j));(i<=k<=j)
这里我们引入一个变量来划分区间，~~初始时f(i,j)是没有意义的，~~
##### 可以注意到上式中用的是~而未用=，是因为上式中并不是等式,至于为什么不是等式，我们就要从f(i,j)的定义出发——f(i,j)表示将从第i堆石子到第j堆石子合并成一堆的最小花费。f(i,k)+f(k+1,j)表示什么？
######  ~~（为了方便我们称 f(i,k)为 x,f(k+1,j) 为 y）~~,f(i,k)+f(k+1,j)表示将x,y和成一堆时的花费，但是合成这两堆（x,y)之前，这两堆也分别是由其他两堆合并出来的，那两堆产生的花费我们并未加进去。

------------

#### 如果你还不理解那么再举一个例子：
##### f(1,2）=f(1,1)+f(2,2)? 很显然不等于，因为此时两者都为0。

------------

#### 那么等式右边缺失的一部分是什么呢？就是合并两堆（x,y)之前的花费
##### 这里就用到前缀和，s[i]表示从1到第i堆的连续和，最总等式：
##### f(i, j) = min( f(i ,j) , f(i,k) + f(k+1,j) + s[i] - s[i-1]);
![](/image_editor_upload/20230207/20230207120130_76310.png)
######  先来个特殊的，对于最终结果是什么？是将1~n堆石子合并成一堆的最小花费，那么不就是f(1 , n) ~~f( i , j)的定义~~
###### f(1，n)=f(i , k)+ f (k +1, j)+x,那么这个x不就是所有石子的和嘛，因为对于最总结果每个石子都被合并了就是s[n]-s[0] (0)
######  一般的：f(i, j)=f(i,k)+f(k+1,j）+x,对于f(i,j)第i~j堆的石子肯定被合并了，所以x=s[j]-s[i-1]；

------------

#### 代码：

```c
    #include <iostream>
    #include <cmath>
    using namespace std;
 
    const int N=110;
    int f[N][N];
    int s[N];
    
    int n;
    int main(){
       cin>>n;
       for(int i=1;i<=n;i++){
           int m;
           cin>>m;
           s[i]=s[i-1]+m;
       }
       for(int len=2;len<=n;len++)
           for(int i=1;i+len-1<=n;i++) {             //左端点
               int j = i + len - 1;                       //右端点
			   //因为下面取得是最小值，所以初始化要大
               f[i][j] = 1e9;                           
               for (int k = i; k < j; k++)               //中间的点
                   f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
               f[i][j]+= s[j] - s[i - 1];
           }
       cout<<f[1][n];
        return 0;
    }
    ```
######  如果已经理解这一题的话，那么挑战一下另外一种题型，也是石子合并，只不过要化环为链：
[https://www.luogu.com.cn/problem/P1880](https://www.luogu.com.cn/problem/P1880)

0.0分

4 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

願

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

【计算直线的交点数】（C语言代码）

C二级辅导-等差数列（C语言代码）

模拟计算器（C语言代码）

3060: 合并石子

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

Pascal三角（C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

数列问题（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

简单的a+b （C语言代码）

剔除相关数（C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

願

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

【计算直线的交点数】 （C语言代码）

C二级辅导-等差数列 （C语言代码）

模拟计算器 （C语言代码）

3060: 合并石子

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

Pascal三角 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

数列问题 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

简单的a+b （C语言代码）

剔除相关数 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

【计算直线的交点数】（C语言代码）

C二级辅导-等差数列（C语言代码）

模拟计算器（C语言代码）

　　评论区

Pascal三角（C语言代码）

用筛法求之N内的素数。（C语言代码）

数列问题（C语言代码）

剔除相关数（C语言代码）

众数问题（C语言代码）