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

FISH酱 · 2025-08-17 21:22:56 · 题解

前置知识

你需要了解区间 DP、前缀和，本题为模板题。

思路讲解

题意很清晰，这里不再赘述。

题目提到合并的代价是质量之和，我们不妨预处理前缀和，方便后续求和；我们设 dp_{i,j} 为合并完 i 到 j 的最小代价；接下来开始求解，枚举左端点和右端点，在范围内枚举分割点，划分为两个区间，合并这两个区间，代价为两个区间代价和，加上合并所需代价（质量之和），如果是更优解就更新；动态规划求解完成后输出合并 1 到 n 所需最小代价即可。

代码展示

写的时候注意细节，以下是我的代码：

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define ld long double
#define endl '\n'

int n;
int a[307]; // 质量
int s[307]; // 前缀和
int dp[307][307]; // dp 数组

signed main(){
    memset(dp,inf,sizeof(dp)); // 求最小值，所以初始化为无穷大

    cin >> n; // 读入
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i][i]=0; // 最初一堆石头没有合并，不需要代价
        s[i]=s[i-1]+a[i]; // 计算前缀和
    }

    for(int p=1;p<=n;p++){ // 枚举长度
        for(int i=1;i<=n;i++){ // 枚举左端点
            int j=i+p; // 计算右端点
            if(j>n) continue; // 防越界

            for(int k=i;k<j;k++){ // 枚举分割点
                dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+(s[j]-s[i-1])); // 计算代价，如果更优就更新最小值
            }

        }
    }

    cout<<dp[1][n]; // 输出答案

    return 0; // 完结撒花！
}