题目描述 给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。

思路：我们看a图v0v3v6这个三角形，把这个凸多边形分成了两个部分，第一个部分：v0v1v2v3,第二个部分v3v4v5v6 我们假设t(i,j)代表顶点{vi-1,vi…vj}所形成的凸多边形的最优三角划分的权函数值，为什么要这样表示呢，因为这样才能保证当i,j不相同时至少有三个点形成多边形，然后当i，j相同时，只有两个点，我们就定义此时的t为0 那么看a图的t(1,6)是不是就大于等于t(1,3)+t(4,6)再加上三角形v0v3v6的权值 v3是我们随便取的，我们可以取1到5任一个数，t(1,6)=当k取其中一个数时最小的那个 那么我们由特殊到一般可得递推关系式 #include using namespace std; int n; int a[8][8];//这里我们假定点数不超过8，a代表点之间的权值 int weight(int vi,int vk,int vj )//返回权值的函数 { return a[vi][vk]+a[vk][vj]+a[vi][vj]; } int m(int n,int **t)//t[i][j]代表的是顶点为{v(i-1),v(i)…v(j)}时最佳三角剖分函数值，因为这样能保证分成的多边形至少有三个顶点 { for(int i=1;i