【非常（ ）的一篇题解】（包含数据提供）

【解题背景】
石子合并没思路？太棒了，本蒟蒻也没思路，同道中人啊！（bushi->不是）

好了好了，回归正题。
遇到石子合并，首先不要慌张，其次必须慌张（bushi），毕竟还有更难的《石子合并》。

【题目简述】
一个一维数组（线性排布），相邻元素合并成一个，合成新元素大小记为本次合并费用，然后跟总费用累加。
什么？你说你样例看不懂？不要慌：
记合成总费用为ans.
原数组：1 2 3 4 5
第一次：一二合并，合并费用1+2=3，ans=0+3=3，数组变为3 3 4 5
第二次：三三合并，合并费用3+3=6，ans=3+6=9,数组变为6 4 5
第三次：四五合并，合并费用4+5=9，ans=9+9=18，数组变为6 9
第四次：六九合并，合并费用6+9=15，ans=18+15=33，数组变为15（成为一堆石子）
显然不同的合并方式有不同的总费用，以上是合并费用最小的方式。
本题的n不是很大，n<1005。

【思考算法】
默默看了一眼标签，居然是动规！！！这咋动规啊？重叠子问题是啥？搜索树咋画？我没见过啊！好怀念最长递增子序列啊。
没错，它不是线性dp也不是数位dp更不是树状dp也不是状压dp，它是【区间dp】！！！
（你肯定还不知道这题其实还能用贪心）
XXX：区间dp是什么？我只会树图dp。
YYY:6，引用一下大佬的话：
区间动态规划，及其变 种环形动态规划。这两类动态规划的特点是，囿于问题本身限制，“某类有序事件中前若干个事 件的子答案”不再能支撑状态转移，我们需要去寻找“从某个元素起到另一个元素结束所包含所 有的（连续）元素的子答案”作为状态。
可以想象，在这个描述下，每个状态会对应于原题序列上的一个区间。区间具有良好的性 质：短的区间可以拓宽成长的区间，相同长度的区间互相不包含。这样，可以把所有状态理解成 DAG，即不会有可以互相到达的局面。
XXX：我盲猜你也懵b了。
YYY：举个【栗】子，for example：就这题，你可以这样定义状态

定义状态f[i][j]表示合并第i堆到第j堆的石子所用的最小费用

很显然，这个i不是从1开始的，而是从n开始递减到1的（画完f数组表格思考一会儿你就会发现）
因为最初肯定是单独一堆石子，给出第二堆后然后两堆合并，所以你想知道f[i][j]的值就可以考虑枚举一个k，用整体思想将其化成两堆合为一堆的过程，即状态转移。
在此之前，我们肯定需要一个op数组来记录第i堆到第j堆合并后的石子堆的石子数，好计算费用。
从而得到状态转移方程：

op[i][j]=op[i][j-1]+a[j];
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+op[i][j])
(i<=j,i<k+1<=j)

状态初始值就很容易想到了，op[i][i]=a[i],自己单独一堆；f[i][i]=0,不合并时费用为0。
（a[i]为第i堆的石子个数）

答案就是从第1堆到第n堆的最小费用，即f[1][n]。注意！很多人的错就在于这个k。

【AC代码】

#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const ll N=1005;
ll n,m=0,i,j,k,a[N],f[N][N],op[N][N];
int main()
{   
    cin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f[i][j]=1061109567;//其它费用大一点，方便比较
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        op[i][i]=a[i];
        f[i][i]=0;
    }
    for(i=n-1;i>=1;i--)
        for(j=i+1;j<=n;j++)//因为要用f[i][k]和f[k+1][j]，需要提前算好，所以注意转移顺序
        {
            op[i][j]=op[i][j-1]+a[j];
            for(k=i;k<j;k++)
                f[i][j]=min(f[i][k]+f[k+1][j]+op[i][j],f[i][j]);//状态转移
        }
    cout<<f[1][n];
    return 0;
}

【题后思考】
三重循环，O（n^3)左右时间复杂度都过了，这题还是太水了。（bushi）
石子合并加强版：如果石子堆不是线性排布而是环形排布呢？就要考虑【破环成链】。
石子合并核聚变式ProMax加强版：题目与本题一样，但1<=n<=40000，ai<=200,时间限制1s，空间限制125MB。

【数据提供】
样例输入#1

5
1 2 3 4 5

样例输出#1

33

样例输入#2

4
1 1 1 1

样例输出#2

8

样例输入#3

5
186 64 35 32 103

样例输出#3

852

样例输入#4

20
32 -24 46 69 124 79 -150 95 188 55 -88 10 49 -62 98 138 185 129 -188 150 

样例输出#4

2763

样例输入#5（拓展1-环形石子合并数据）

20
32 -24 46 69 124 79 -150 95 188 55 -88 10 49 -62 98 138 185 129 -188 150 

样例输出#5（拓展1-环形石子合并数据）

2573

样例输入输出#6（拓展2-石子合并加强数据）
（要的话请站内消息私发找我要，数据太大，这里上传不了，建议你发我数据我给你答案）
《我应该会回复，但应该要一些时间》