GroupBlog

题目描述：

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。

Input

第1行：N（2 <= N <= 100)
第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)

Output

输出最小合并代价

Input示例

4
1
2
3
4

Output示例

思路：
递归定义合并A，B两堆石子的代价：合并A堆的代价+合并B堆的代价+A堆石子重量+B堆石子重量。
于是有阶段：石子每次合并的过程

状态：每一阶段中各个不同合并方法的石子合并总得分。

决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案具体来说我们应该定义一个数组dp[start][end]用来表示合并方法，dp[start][end]表示从第start堆开始到end堆进行合并，dp[1][n]为合并的最优得分。其中start和要合并的长度确定了，end也就确定，不用end进行迭代。

思考：在过程中，任何一堆石子都是有两堆合并而来的，假设过程刚开始时，是将给出的相邻的第i堆和第i+1堆合并。过程最后是将，从第1到k堆合并成的一堆(1)，与从k+1堆到n堆合并成的一堆(2)，
(1)(2)这两堆合并的。

所以有状态转移方程：

dp[start][start+len] =
min(dp[start][k]+dp[k+1][start+len]+∑a[start~start+len]) ;
(start<=k < start+len), len为要合并的堆数（1～n）

/********************************************
    > File Name: 1048.cpp
    > Author: dulun
    > Mail: dulun@xiyoulinux.org
    > Created Time: 2016年03月06日 星期日 16时37分29秒
********************************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 1086;
int dp[N][N];
int a[N];
int sum[N];

int main()
{
    int n; 
    cin>>n;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
        sum[i] = sum[i-1]+a[i];
    }

    for(int l = 2; l <= n; l++)
    {
        for(int start = 1; start <= n - l + 1; start++)
        {
            int end = start+l - 1;
            int min = 1<<30;
            for(int k = start; k < end; k++)
            {
                if(dp[start][k]+dp[k+1][end] + sum[end] - sum[start-1] < min)
                    min = dp[start][k]+dp[start+1][end]+sum[end]-sum[start-1];
            }
            dp[start][end] = min;
        }
    }
    cout<<dp[1][n]<<endl;

    return 0;
}