题目描述
众所周知，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为答案。
题目分析
首先这种最值问题比较容易判断出是贪心还是dp，显然这里的划分图的步骤是具有后续性的，dp成为了我们的首选。
那么问题就来到了如何给出状态转移方程，根据dp一般的手法，我们首先记数组dp[i][j]为图当中从第\(i\)个点到第\(j\)个点所圈定的\(j-i+1\)边形当中划分所得的最大值
容易发现
当\(i=j\)时：\(dp[i][j]=0\)。
当\(j-i=1\)，也就是恰夹一个点组成三角形时，\(dp[i][j]=a[i]*a[j]*a[j+1]\)
当\(j-i>=2\)时，我们就会用到之前的情况。注意，如果设\(j-i=r\)，我们其实已经求取出了在当前\(i\)之后的所有\(j-i<r\)的情况。我们需要较之前多增加一条边那么这多出来一条边必然会多出一个连接的点位，我们不妨设一个点\(k\)从\(k=i+1\)开始遍历，每一次我们均比较\(dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]\)与原先的\(dp[i][j]\) ，取大值即可。
上式中左侧三项分别代表 (\(k\)左侧的已经划分出的最优解) (\(k\)右侧的已经划分出的最优解) (这一点\(k\)与\(i\)和\(j\)所共同组成的三角形的值)
综上可得状态转移方程为
$$dp[i][j]=max(dp[i][j],max(dp[i][k]+dp[k][j]+a[i]*a[j]*a[k])(i<k<j))$$
每一次都从\(i\)点循环操作至\(n-1\)最终我们就可以得到从\(0\)到\(n-1\)的最优解\(dp[0][n-1]\)
Accepted Code
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-03-14 20:02:34
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int a[105];
int main()
{
int t, op = 1;
cin >> t;
while (t--)
{
memset(dp, 0, sizeof(dp));
memset(a, 0, sizeof(a));
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = n - 3; i >= 0; i--)
{
for (int j = i + 2; j < n; j++)
{
for (int k = i + 1; k < j; k++)
{
dp[i][j] = max(dp[i][j], (dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]));//循环更新
}
}
}
printf("Case #%d: %d\n", op++, dp[0][n - 1]);//注意输出格式
}
return 0;
}