题目来源：中国石油大学ACM俱乐部开放训练题

题目介绍：

众所周知，sciorz会画画。某天，sciorz画了一个凸多边形，这个多边形的每个顶点有一个权值a[i]。sciorz觉得这个凸多边形不够美丽，于是他决定在n个点之间连线，最终用n-3条不相交的线将这个凸多边形分隔成n-2个三角形。sciorz认为，一个三角形的美丽值是三个顶点权值的乘积，凸多边形的美丽值是其内部三角形美丽值之和。sciorz想到了一种分割方案，使这个凸多边形的美丽值最大，sciorz忙着刷题，所以他随手就把这个签到题扔给你，希望你帮sciorz算出最大的美丽值。

输入：

第一行一个t，表示有t组样例。 每组样例的第一行是一个n，表示多边形的边数。 第二行n’个数，第i个数表示多边形第i个顶点的权值a[i]，按逆时针方向给出。

输出：

对于每组样例，输出一行。格式为“Case #x:y”，x为样例编号，y为答案。

样例输入：

2 3 1 2 3 4 1 2 3 4

样例输出：

Case #1:6 Case #2:32

原理：

dp[i][j]表示从i到j的最优剖分方案，其中，当j=i或j=i+1时无法构成三角形；当j>=i+2时可以构成三角形，此时定义一个分割点k，将整个凸多边形分成三个部分，ik部分，kj部分和三角形ikj，然后运用递归分别求解ik和kj部分，最后求其最大值。

代码实现：

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
39
import java.util.Scanner;

public class sciorz {
    public static int max;//用来存储最大值
    public static int n;//存储凸多边形边数
    public static int[] a=new int[100];//存储各个点的权值
    public static int dp(int i,int j){
        max=0;
        for(int k=i+1;k<j;k++) {
            int temp = dp(i, k) + dp(k, j)+a[i]*a[j]*a[k];
            //如果值大于max则交换
            if(temp>max){
                max=temp;
                return max;
            }
            return max;
        }
        return max;
    }

    public static void main(String[] args) {
        int t;
        //创建Scanner输入
        Scanner kb=new Scanner(System.in);
        //输入共有t组数据
        t=kb.nextInt();
        for(int l=0;l<=t;l++){
            //输出序号
            int x=l+1;
            //存入凸多边形边数
            n=kb.nextInt();
            for(int i=0;i<n;i++)
                a[i]=kb.nextInt();
            dp(0,n-1);
            //输出结果
            System.out.println("Case #"+x+":"+max);
        }
    }
}