石子合并
time limit per test 1 second memory limit per test 256 megabytes
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

传送门：NYOJ737

Input

有多组测试数据，输入到文件结束。每组测试数据第一行有一个整数n，表示有n堆石子。接下来的一行有n（1≤n≤199）个数，分别表示这n堆石子的数目，用空格隔开

Output

输出总代价的最小值，占单独的一行

Sample Input

1
2
3
4
3
1 2 3
7
13 7 8 16 21 4 18

Sample Output

1
2
9
239

题解

学习了一波四边形不等式 对于 f[i][j]= min{f[i][k]+f[k+1][j]+w[i][j]}
凸四边形不等式：w[a][c]+w[b][d]<=w[b][c]+w[a][d] a<b<c<d 区间包含关系单调: w[b][c]<=w[a][d] a<b<c<d 定理1： 如果w同时满足四边形不等式和决策单调性 ,则f也满足四边形不等式 定理2： 若f满足四边形不等式，则决策s满足 s[i][j-1]<=s[i][j]<=s[i+1][j] 定理3： w为凸当且仅当w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]
s代表方案取的下标 初始s[i][i]=i 这样能把O(n^3)的dp化为O(n^2)
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.*;  
import java.util.*;  
public class Main {  
    static int maxn=(int) (1e9+7);  
    public static void main(String[] args) {  
        FastScanner sc = new FastScanner();  
        PrintWriter pw = new PrintWriter(System.out);  
        while (sc.hasNext()) {  
            int n=sc.nextInt();  
            int[]shu=new int[n+1];  
            for(int i=1;i<=n;i++)shu[i]=sc.nextInt();  
            int[][]dp=new int[n+1][n+1];  
            int[][]s=new int[n+1][n+1];  
            for(int i=1;i<=n;i++)Arrays.fill(dp[i], maxn);  
            for(int i=1;i<=n;i++){  
                dp[i][i]=0;  
                s[i][i]=i;  //初始化方案取的下标
            }  
            int[]pre=new int[n+1];  
            for(int i=1;i<=n;i++){  
                pre[i]=pre[i-1]+shu[i];  
            }  
            for(int j=1;j<=n;j++){  
                for(int i=j-1;i>=1;i--){  
                    for(int k=s[i][j-1];k<=s[i+1][j];k++){  
                        int temp=dp[i][k-1]+dp[k][j]+pre[j]-pre[i-1];  
                        if(temp<dp[i][j]){  
                            dp[i][j]=temp;  
                            s[i][j]=k;  
                        }  
                    }  
                }  
            }  
            pw.println(dp[1][n]);  
            pw.flush();  
        }  
    }  
}