石子合并

题目 石子合并

思路分析

类似于归并排序 每次都是左右两个区间进行合并

所以可以用f[i][j]表示i到 j这一段石子合并成一堆的方案的集合，属性 Min

每次合并其实就是对左边区间f[i][k]所需要的最小代价加上右边区间f[k+1][j]的最小代价 再加上本次合并的代价——i到j的价值数 这个可以用前缀和实现：s[j]

• s[i - 1]

由此状态转移方程：f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);

考虑初始化边界情况

当 i=j的时候 代价为0 表示合并一堆石头代价为0

最后答案应该就是f[1][n]

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=307;

int a[N],s[N];

int f[N][N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>a[i];

        s[i]=s[i-1]+a[i];

    }

    memset(f,0x3f,sizeof f);

    for(int len=1;len<=n;len++){ // 枚举区间长度

        for(int i=1;i+len-1<=n;i++){// 枚举起点

            int j=i+len-1;

            if(len==1){

                f[i][j]=0;

                continue;

            }

            for(int k=i;k<=j-1;k++){// 枚举分割点，构造状态转移方程

                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

            }

        }

    }

    cout<<f[1][n];

    return 0;

}

同类题型

视频讲解

⬅️ 环形石子合并 🏠 00-刷题理模型 ➡️ 能量项链