51Nod 1021 石子归并（动态规划）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <iostream>
 5 
 6 #define INF 0xfffffff
 7 using namespace std;
 8 const int maxn = 100 + 5;
 9 int a[maxn];
10 int sum[maxn];
11 int dp[maxn][maxn];
12 //dp[i][j]    从i到j所需的最少
13 
14 int main(){
15     ios::sync_with_stdio(false);
16     /*
17     freopen("in.txt", "r", stdin);
18     freopen("out.txt", "w", stdout);
19     */
20     int n;
21     cin >> n;
22     for (int i = 1; i <= n; i++){
23         cin >> a[i];
24         sum[i] = sum[i - 1] + a[i];
25     }
26     //init
27     
28     for (int l = 2; l <= n; l++){
29         //中间的长度
30         for (int sta = 1; sta <= n - l + 1; sta++){
31             int endd = sta + l - 1;
32             int Min = INF;
33             for (int k = sta; k < endd; k++){
34                 if (dp[sta][k] + dp[k + 1][endd] + sum[endd] - sum[sta - 1] < Min){
35                     Min = dp[sta][k] + dp[k + 1][endd] + sum[endd] - sum[sta - 1];
36                 }
37             }
38             dp[sta][endd] = Min;
39         }
40     }
41     cout << dp[1][n] << endl;
42     
43     //fclose(stdin);
44     //fclose(stdout);
45     system("pause");
46     return 0;
47 }