凸多边形的划分

10149

题目描述

有一个(N)个顶点的多边形，每个顶点都有一个权值，求如何划分使得划分后的(N-2)个三角形的权值乘积和最小。

思路

这题本意是要写高精度的，不过这不是重点。我们考虑用(f[i][j])表示以(i)和(j)之间的顶点所构成的多边形的最小权值乘积和，那么我们考虑作为((i,j))这条边，必定有一个顶点与这条边形成一个三角形，我们枚举这个点，就把这个多边形分成了两个多边形，再加上这个三角形堆答案的贡献即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;

ll read()
{
	ll res=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
	return res*w;
}
void write(ll x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
void writeln(ll x)
{
	write(x);
	putchar('
');
}

ll f[110][110],a[110];
int main() 
{
	int n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),a[i+n]=a[i];
	memset(f,127,sizeof(f));
	for(int i=1;i<n*2;i++)
		f[i][i+1]=0;
	for(int len=3;len<=n;len++)
		for(int l=1;l<=n*2-len+1;l++)
		{
			int r=l+len-1;
			for(int k=l+1;k<r;k++)
				f[l][r]=min(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
		}
	ll ans=f[1][n];
	for(int i=1;i<=n;i++)
		ans=min(ans,f[i][i+n-1]);
	write(ans);
	return 0;
}