问题 A: sciorz画画

时间限制: 1 Sec  内存限制: 128 MB
提交: 845  解决: 159
[状态] [提交] [命题人:外部导入]

题目描述

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

输入

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

输出

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

样例输入 Copy

2
3
1 2 3 
4
1 2 3 4

样例输出 Copy

Case #1: 6
Case #2: 32

提示

第一个样例只有一个三角形，所以不用分割，答案是1*2*3=6。
第二个三角形，最优分割方案是分割为1 2 4和2 3 4两个三角形，答案是1*2*4+2*3*4=32

1<=t<=100
3<=n<=100
１<=a[i]<=100

 

参考：

https://www.cnblogs.com/Jason-Damon/p/3298172.html

https://www.cnblogs.com/wkfvawl/p/11631227.html

 

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 120;

int a[N];
int dp[N][N];   ///最优权值
int s[N][N];    ///s[i][j]为点i和点j组成三角形的第三个点

int weight(int i, int j, int k) ///权函数值
{
    return a[i] * a[j] * a[k];
}

int main()
{
    int n, t, kcase = 0;
    scanf("%d", &t);
    while(t--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
        }
        for(int r = 2; r <= n; ++r)  ///枚举两点间距
        {
            for(int i = 1; i <= n - r + 1; ++i)  ///第一个点
            {
                int j = i + r - 1;      ///第二个点
                int maxx = 0;           ///以i, j为顶点组成三角形的最大权值
                for(int k = i; k < j; ++k)  ///枚举第三个点与i, j组成三角形
                {
                    dp[i][j] = dp[i][k] + dp[k + 1][j] + weight(i - 1, k, j);
                    if(dp[i][j] > maxx)
                    {
                        maxx = dp[i][j];
                        s[i][j] = k;
                    }
                }
                dp[i][j] = maxx;
            }
        }
        cout<<"Case #"<<++kcase<<": "<<dp[1][n]<<'\n';
    }
    return 0;
}