题目描述
众所周知,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
提示
第一个样例只有一个三角形,所以不用分割,答案是123=6。
第二个三角形,最优分割方案是分割为1 2 4和2 3 4两个三角形,答案是124+234=32
1<=t<=100
3<=n<=100
1<=a[i]<=100
这题是真不会,训练的时候,通过好多次试出来的。。。
后来补了一下这方面的理论。
设 dp [ i ] [ j ] 是取第 i 个顶点到第 j 个顶点所组成的凸多边形的最大值。
那么 dp [ i ] [ j ] = max ( dp [ i ] [ k ] + dp [ k ] [ j ] + a [ k ] * a [ i ] *a [ j ] ) 就相当于多了i,j,k这个三角形。
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#define ll long long
using namespace std;
const int maxn=110;
const int mod=1000000007;
int dp[maxn][maxn];
int a[maxn];
int main(void)
{
int t;
scanf("%d",&t);
int pp=0;
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
memset(dp[i],0,sizeof(dp[i]));
}
for(int len=3;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int k=l+1;k+1<=r;k++)
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[r]*a[k]);
}
}
printf("Case #%d: %d\n",++pp,dp[1][n]);
}
return 0;
}