nyoj737 石子合并（一）（区间dp）

题目737 题目信息 运行结果 本题排行 讨论区

石子合并（一）

时间限制： 1000 ms  |  内存限制： 65535 KB 难度： 3 描述     有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。 输入 有多组测试数据，输入到文件结束。 每组测试数据第一行有一个整数n，表示有n堆石子。 接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开 输出 输出总代价的最小值，占单独的一行 样例输入 3 1 2 3 7 13 7 8 16 21 4 18 样例输出 9 239 来源 经典问题 上传者 TC_胡仁东 学习算法设计时有一道 矩阵连乘问题。 和这道题类似 题意：用最小的代价把所有石子堆为一堆。 解题思路： 很经典的区间DP问题。 既然每次都能把相邻的两堆石子堆为一堆，那么对于这道题而言求解的方法就是找到堆石子的次序。 动态规划能很好的解决这个问题。 假设dp[i][j]表示第i个石子到第j个石子堆为一堆所花费的最小代价。 由于要找到堆石子的次序，那么在i和j之间假设断点为k 则   dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+incre)。incre表示在k点断开，合并两堆石子多出的代价。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int main() { int n; int a[205]; int sum[205]; int dp[205][205]; while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } //合并石子的长度 for(int l=2;l<=n;l++) { //石子的左端 for(int i=1;i<=n;i++) { //石子的右端 int j=i+l-1; if(j>n)break; //断点为i,j dp[i][j]=min(dp[i+1][j]+a[i]+sum[j]-sum[i],dp[i][j-1]+a[j]+sum[j-1]-sum[i-1]); //i-j的断点 for(int k=i+1;k<j;k++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]-sum[i-1]+sum[j]); } } } printf("%d\n",dp[1][n]); } return 0; }