wikioi 1048 石子归并

dp[i][j]=min(dp[i][j],dp[i][k],dp[k+1][j]+sum[i][j]);
表示i-j的最小合并代价。
 1     #include <iostream>  
 2     #include <string.h>  
 3     #include <stdio.h>  
 4       
 5     using namespace std;  
 6     const int INF = 1 << 30;  
 7     const int N = 205;  
 8       
 9     int dp[N][N];  
10     int sum[N];  
11     int a[N];  
12       
13     int getMinval(int a[],int n)  
14     {  
15         for(int i=0;i<n;i++)  
16             dp[i][i] = 0;  
17         for(int v=1;v<n;v++)  
18         {  
19             for(int i=0;i<n-v;i++)  
20             {  
21                 int j = i + v;  
22                 dp[i][j] = INF;  
23                 int tmp = sum[j] - (i > 0 ? sum[i-1]:0);  
24                 for(int k=i;k<j;k++)  
25                     dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + tmp);  
26             }  
27         }  
28         return dp[0][n-1];  
29     }  
30       
31     int main()  
32     {  
33         int n;  
34         while(scanf("%d",&n)!=EOF)  
35         {  
36             for(int i=0;i<n;i++)  
37                 scanf("%d",&a[i]);  
38             sum[0] = a[0];  
39             for(int i=1;i<n;i++)  
40                 sum[i] = sum[i-1] + a[i];  
41             printf("%d
",getMinval(a,n));  
42         }  
43         return 0;  
44     }