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

前置知识

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

思路讲解

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

题目提到合并的代价是质量之和，我们不妨预处理前缀和，方便后续求和；我们设

dp_{i,j}

为合并完

i

到

j

的最小代价；接下来开始求解，枚举左端点和右端点，在范围内枚举分割点，划分为两个区间，合并这两个区间，代价为两个区间代价和，加上合并所需代价（质量之和），如果是更优解就更新；动态规划求解完成后输出合并

1

到

n

所需最小代价即可。

代码展示

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

CPP

#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; // 完结撒花！
}

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

文章操作

前置知识

思路讲解

代码展示

相关推荐

评论

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