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

· · 题解

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

思路

区间动态规划，从小到大 DP 不同的长度的合并最小代价，层层递进，得到长度为 n 的合并最小代价。

状态转移方程
dp[i][i]=0 (1 \le i \le n) dp[l][r]= \min (dp[l][r],dp[l][mid]+dp[mid+1][r]+sum[r]-sum[l-1]) (1 \le l \le mid < r \le n)

代码

#include <bits/stdc++.h>
using namespace std;
//dp[i][j]石子i~j全部合并的最小代价
int dp[310][310],sum[310];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,0x3f,sizeof dp);//在求min之前一定要赋无穷大
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1];//前缀和
        dp[i][i]=0;//石子i在合并前没有代价
    }
    //第一层：区间长度
    for (int len=2;len<=n;len++){
        //第二层：左端点
        for (int l=1;l<=n-len+1;l++){
            //右端点=左端点+长度-1
            int r=l+len-1;
            //第三层：左右堆的界限
            //左堆：l~mid，右堆：mid+1~r
            for (int mid=l;mid<r;mid++){
                //每次都要更新最小值
                //dp[l][mid]左堆的最小代价
                //dp[mid+1][r]右堆的最小代价
                //sum[r]-sum[l-1]左右堆的质量和，即这次合并的代价
                dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]+(sum[r]-sum[l-1]));
            }
        }
    }
    cout<<dp[1][n];//区间1~n的合并最小代价
    return 0;
}