石子歸并（dp + 四邊形不等式優化）

題目

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 <= 1000)

第2 - N + 1：N堆石子的數量（1 <= Aii <= 10000)

Output

輸出最小合并代價

Sample Input

4

1

2

3

4

Sample Output

19

優化講解：點選這裡

這道題，用之前的老方法是會逾時的，需要一個“四邊形不等式優化”方法，方法大概是看懂了，但是具體的推理過程我沒有看懂，覺得看着挺複雜的，本來想着我這樣的想法和做法應該是很不好的，但是我們打ACM的又不是搞數學推理研究的，非太大的精力去吧那些很複雜的數學推理弄明白，沒有太大的意思。

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;

int s[][];//表示->j之間的最優分割點的位置
void demo(int dp[][], int *arr, int n)
{
    for (int i = ; i <= *n-; i++)
    {
        s[i][i] = i;
        for (int j = ; j <= *n-; j++)
            dp[i][j] = (i == j)?  : e9;
    }
    for (int i = *n-; i >= ; i--)
        for (int j = i+; j <= *n-; j++)
            for (int k = s[i][j-]; k <= s[i+][j]; k++)
            {
                int temp = dp[i][k] + dp[k+][j] + arr[j] - arr[i-];
                if (dp[i][j] > temp)
                {
                    dp[i][j] = temp;
                    s[i][j] = k;
                }
            }

}

void get_min_cost(int dp[][], int n, int &min_cost)
{
    min_cost = e9;
    int index = ;

    while(n+index- <= *n-)
    {
        min_cost = min(min_cost, dp[index][n+index-]);
        index++;
    }
}

int main()
{
    int n;
    int min_cost = ;
    int arr[];
    static int dp[][];

    scanf("%d", &n);
    arr[] = ;
    for (int i = ; i <= n; i++)
    {
        scanf("%d", &arr[i]);
        arr[i+n] = arr[i];
    }

    for (int i = ; i <= *n-; i++)
        arr[i] += arr[i-];

    demo(dp, arr, n);
    get_min_cost(dp, n, min_cost);

    printf("%d\n", min_cost);

    return ;
}