题解：P1775 石子合并（弱化版）

Yxa_Sheep · 2025-08-21 09:35:09 · 题解

题目传送门

题意

有 n 个质量为 a_i 的石子，合并相邻的两堆代价为两堆石子的质量之和，求最小代价。

思路

一道区间 DP 的水题。

• 状态定义：f_{i,j} 表示从第 i 堆到第 j 堆合并成一堆的最小代价。
• 初始化 DP 数组：因为我们要求最小值，所以需要将 DP 数组初始为极大值。显然，每一堆合并成自己的代价为 0，所以 f_{i,i}=0。
• 状态转移：由第 i 堆到第 j 堆的合并成一堆后这一堆的质量肯定是 a_i+a_{i+1}+\dots+a_{j-1}+a_j，那么我们知道了第 i 堆合并到第 j 堆的最小代价为 f_{i,j}，再枚举一个 k，很明显 f_{i,k} 加上 f_{k+1,j} 再加上新的代价，也就是从第 i 堆到第 k 堆合并成一堆的大小加第 k+1 堆到第 j 堆合并成一堆的大小。综上可以得到 f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}+a_i+a_{i+1}+\dots+a_{j-1}+a_j) 这个状态转移方程
• 优化：这里的 a_i+a_{i+1}+\dots+a_{j-1}+a_j 不难让我们想到前缀和，于是 f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}+sum_j-sum_{i-1}) 就是最终状态转移方程。
• 具体实现：用三重循环枚举，第一重枚举合并段的长度 len，第二重枚举合并段的起始位置 i，并且可以确定结束位置 j 为 i+len-1，第三重循环枚举 k，以确定 f_{i,j} 的值。具体细节见代码。

  代码

  #include <bits/stdc++.h>
  #define code using
  #define from namespace
  #define Yxa_Sheep std
  code from Yxa_Sheep;
  int n, a[310], sum[310], f[310][310];
  int main()
  {
  scanf("%d", &n), memset(f, 0x3f, sizeof f);
  for (int i = 1; i <= n; i++)
      scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i], f[i][i] = 0;
  for (int len = 2; len <= n; len++)
      for (int i = 1; i + len - 1 <= n; i++)
      {
          int j = i + len - 1;
          for (int k = i; k < j; k++)
              f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
      }
  printf("%d", f[1][n]);
  return 0;
  }

做完此题的可以去这里：P1880 [NOI1995] 石子合并。

题解来之不易，且看且珍惜。点个赞再走吧。

题目传送门