题目概述

n 堆石子 将 n 堆堆石子合并成为一堆。每次只能合并相邻的两堆。

C++

#include <algorithm>
#include <iostream>

using namespace std ;

const int N = 310;

int n;
int s[N];   //s[i]存的是第i堆石子的重量
int f[N][N];//f[i][j]表示合并第i堆至第j堆石子的代价

int main()//分治思想
{
    scanf("%d",&n);
    for(int i =1;i<=n;i++) scanf("%d",&s[i]);//读数据

    for(int i =1;i<=n;i++) s[i] += s[i-1] ;
    //使用前缀和，第方便表示一个区间的所有的代价
    for(int len = 2;len <=n;len++)//相当于架构单位，从最小的单位长度2开始架构
     for(int i =1; i+ len - 1<=n;i++)
     {
         int l = i,r = i+len - 1;//左右端点
         f[l][r] = 1e8;//初始化成一个正无穷
         for(int k = l; k< r;k++)
         f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
         // k相当于隔板位置，每个父堆来自两个相邻的子堆
         //f[l][k]是合并成从l小堆至k小堆的这个子堆代价
         //f[k+1][r]是合并成从k+1小堆至r小堆的这个子堆代价
         //加上s[r]-s[l-1]是利用前缀和求出的本次合并的代价
     }
     //解释一下架构单位的意思
     //举例来说
     //由5个堆合并的堆必来自于1+4，2+3
     //也就是说要想知道由5个堆合并的最小值就必须知道 1，2，3，4个堆合成堆中各自的最小值
     //故从最小的开始枚举构造
     printf("%d\n",f[1][n]);
     return 0;

}