首页 > 代码库 > 最小代价 子母树
最小代价 子母树
题目描述 Description
在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将N堆石子合并成一堆的最小得分。
输入描述 Input Description
第一行是一个数N。
以下N行每行一个数A，表示石子数目。
输出描述 Output Description
共一个数，即N堆石子合并成一堆的最小得分。
样例输入 Sample Input
4
1
1
1
1
样例输出 Sample Output
8
数据范围及提示 Data Size & Hint
对于 30% 的数据，1≤N≤100
对于 60% 的数据，1≤N≤1000
对于 100% 的数据，1≤N≤40000
对于 100% 的数据，1≤A≤200
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>#include<queue>#include<set>#include<vector>using namespace std;#define INF 1<<30int n,a[110],dp[110][110],sum[110];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; for(int len=2;len<=n;len++) { for(int i=1;i<=n-len+1;i++) { int j=i+len-1; int minn=INF; for(int k=i;k<j;k++) { if(minn>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]) minn=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]; } dp[i][j]=minn; } } printf("%d\n",dp[1][n]); return 0;}
最小代价 子母树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。