石子合并三大题型

  1. 任意两堆石子合并，直接手写一个小根堆，每次取前面两个相加，得到的值继续放入优先队列中，直到里面只有一个元素就输出
  2. 只能合并相邻两堆石子，这就类似于矩阵连乘（传送门），不过还是有一些差别
  3. 在2的基础上，这些石子形成一个环形，这又是一种新的题型

今天记录的是第二种——区间dp

题目描述
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。例如：输入{1，2，3，4，5}，输出33。【3+6+9+15=33】
输入
本题应该处理到文件尾，每组输入包括两行，第一行为石子堆的个数n，第二行则为每堆石子的个数。
输出
输出最小花费。
样例输入
5
1 2 3 4 5
样例输出
33

ps：

首先分析一下这个题目，举个例子，如果只有三堆 4 ， 5 ， 9
我们合并这三堆所花费的来自三部分

  • 第一二堆合并的花费
  • 第一二堆石子的个数和
  • 第三堆石子的数量
  • 那么就是4+5+9+6=24

但是这个题目要求的是相邻两堆之间合并，如果又很多堆石子，那么我们就要去找断点，最优值问题就是一个个最优子结构，所以我们需要一个一个去找断点，算出每一个最优子结构，然后相加

转移方程如下


此外我们需要引入一个数组，来记录石子的数量，可以利用前缀和思想，也可以直接存储第i到第j石子的数量


前缀优化

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int a[maxn], b[maxn], dp[maxn][maxn];
int main()
{
   
   int n;
   while (~scanf("%d", &n))
   {
   
      memset(dp, 0, sizeof(dp));
      for (int i = 1; i <= n; ++i)
         scanf("%d", &a[i]), b[i] = b[i - 1] + a[i]; //b数组求前缀
      for (int l = 2; l <= n; ++l)
      {
   
         for (int i = 1; i + l - 1 <= n; ++i)
         {
   
            int j = i + l - 1;
            dp[i][j] = inf;
            int x = b[j] - b[i - 1]; //i到j区间的石子数
            for (int k = i; k < j; ++k)
            {
   
               dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + x);
            }
         }
      }
      printf("%d\n", dp[1][n]);
   }
   return 0;
}


利用数组存取石子的数量，和矩阵相乘类似，只是把乘换成加了 
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
//#define inf 1<<20
const int maxn = 210;
int n, a[maxn];
int dp[maxn][maxn];  //dp[i][j]表示从第i堆到第j堆合并的代价
int sum[maxn][maxn]; //表示石头的数量
int main()
{
   
    while (cin >> n)
    {
   
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            sum[i][i] = a[i], dp[i][i] = 0;
        for (int len = 2; len <= n; len++)
        {
    //区间长度
            for (int i = 1; i + len - 1 <= n; i++)
            {
                           //区间起点
                int j = i + len - 1; //区间终点
                dp[i][j] = inf;
                for (int k = i; k <= j; k++) //用k来表示分割区间
                {
   
                    sum[i][j] = sum[i][k] + sum[k + 1][j];
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}
人生如一场修行，得意时， 一日看尽长安花，艰难时，潦倒新停浊酒杯，但生命的跋涉不能回头，哪怕，畏涂巉岩不可攀，也要会当临绝顶，哪怕无人会登临意，也要猛志固常在，从经典中汲取九万里风鹏正举的力量，历练也无风雨也无晴的豁然，待到重阳日，我们还来就菊花。

若干年看到这些图片不知会作何感想