石子合并

链接：282. 石子合并 - AcWing题库

题面：

思路：

代码：

#include

using namespace std;

typedef long long ll;

const int N=310;

int n,a[N],sum[N],f[N][N];

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];



    //前缀和求法

    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    //计算[l,r]的前缀和公式：sum[r]-sum[l-1]

    //区间长度从小到大遍历

    for(int len=2;len<=n;len++)//长度为1的时候就是不做合并，即从2开始循环

    {

        for(int i=1;i+len-1<=n;i++)

        {

            int l=i,r=i+len-1;

            f[l][r]=1e8;//这里要求的是最小值，所以初始值赋值一个较大的数

            for(int s=l;s