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

题目传送门

题意

思路

• 状态定义：$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] 石子合并。

题目传送门