本文共 911 字，大约阅读时间需要 3 分钟。

石子归并

有N堆石子排成一排,其中第i堆的石子的重量为Ai，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，形成的新石子堆的重量以及消耗的体力都是两堆石子的重量之和。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define ll long long#define inf 0x3f3f3f3fll a[400], sum[400], dp[400][200];int main() {
       int n;    while (scanf("%d", &n) != EOF) {
           for (int i = 1; i <= n; i++) {
               scanf("%d", &a[i]);            sum[i] = sum[i - 1] + a[i];            dp[i][i] = 0;        }        for (int l = 2; l <= n; l++) {
               for (int i = 1; i + l <= n + 1; i++) {
                   int j = i + l - 1;                dp[i][j] = inf;                for (int k = i; k < j; k++) {
                       dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - sum[i - 1] + sum[j]);                }            }        }        printf("%d\n", dp[1][n]);    }}
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108557377 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！