描述
有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据,输入到文件结束。
每组测试数据第一行有一个整数n,表示有n堆石子。
接下来的一行有n(0< n <200)个数,分别表示这n堆石子的数目,用空格隔开
输出
输出总代价的最小值,占单独的一行
样例输入
复制代码
1
2
3
43 1 2 3 7 13 7 8 16 21 4 18
样例输出
复制代码
1
29 239
思路:求出每个区间的最小代价,dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]),dp[i][j]表示i到j的最小代价,a[j]-a[i-1]为两个区间合并的代价。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include<algorithm> #include<string.h> #include<stdio.h> using namespace std; int a[210],dp[210][210]; int main() { int n; while(~scanf("%d",&n)) { memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]+=a[i-1]; dp[i][i]=0; } for(int len=2;len<=n;len++)//控制区间长度 { for(int i=1;i<=n;i++) { int j=i+len-1; if(j>n) break; for(int k=i;k<=j;k++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]); } } } printf("%dn",dp[1][n]); } }
最后
以上就是酷酷人生最近收集整理的关于nyoj737—石子合并(一)(区间DP)的全部内容,更多相关nyoj737—石子合并(一)(区间DP)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复