石子合并问题(一) （基础的区间dp）

石子合并（一）

时间限制：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

来源

经典问题

解题思路：

　　刚刚学会区间dp，感觉区间dp要把握的重点就是要明确dp[i][j] = dp[i][k]+dp[k+1][j]+sum(i,j) 得到的，就是说，

任意一个区间[i,j]都可以由[i,k]和[k+1,j]得到。。。区间dp用的最多的就是记忆化搜索了。。

代码：

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<cstring>
 4 
 5 using namespace std;
 6 
 7 # define MAX 233
 8 # define inf 99999999
 9 
10 int a[MAX];
11 int sum[MAX];
12 int dp[MAX][MAX];
13 
14 int cal ( int i,int j )
15 {
16     if ( dp[i][j] )
17         return dp[i][j];
18     else if ( i==j-1 )
19         dp[i][j] = a[i]+a[j];
20     else if ( i==j )
21         return 0;
22     else
23     {
24         dp[i][j] = inf;
25         for ( int k = i;k <= j;k++ )
26         {
27             int temp = cal(i,k)+cal(k+1,j)+sum[j]-sum[i-1];
28             if ( temp < dp[i][j] )
29             {
30                 dp[i][j] = temp;
31             }
32         }
33     }
34     return dp[i][j];
35 }
36 
37 int main(void)
38 {
39     int n;
40     while ( scanf("%d",&n)==1 )
41     {
42         for ( int i = 1;i <= n;i++ )
43         {
44             scanf("%d",&a[i]);
45             sum[i] = sum[i-1]+a[i];
46         }
47         memset(dp,0,sizeof(dp));
48         int res = cal(1,n);
49         printf("%d
",res);
50 
51     }
52 
53 
54     return 0;
55 }