7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby！！！！！！！！！-Toy模板网

这篇具有很好参考价值的文章主要介绍了7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby！！！！！！！！！。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一：题目：

给定n边凸多边形P，要求确定该凸多边形的三角剖分（将多边形分割成n-2个三角形），使得该三角剖分中诸三角形上权之和为最小。各边弦的权值以由输入数据给出，以无向图的形式表示。三角形的权值等于三条边权值相加。
7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby！！！！！！！！！
输入格式:
第一行输入凸多边形的边数n(3<=n<=8)

第二行起，输入顶点i(1<=i<=n)到顶点j(i<=j<=n)组成的边或弦的权值

输出格式:
最优三角剖分中诸三角形上权值和。

输入样例:

6
0 2 2 3 1 4
0 1 5 2 3
0 2 1 4
0 6 2
0 1
0

输出样例:

二：分析题意：

有没有兄弟搞不清题目当中 使得该三角剖分中诸三角形上权之和为最小这句话，反正我是读了几十遍，没读懂
后来看了一篇博客，上面给解释了，这个也就是当将凸多变形剖分完成后，求取所有三角形的周长和使其最小

三：思路：

1.凸多边形的三角剖分是将凸多边形分割成互不相交的三角
形的弦的集合。
2.最优三角剖分中诸三角形上权值和：指的是将多边形划分成多个三角形
其所有的三角形的周长和最小
3.和矩阵连相乘的思路比较：凸三角形的剖分是通过一个三角形将多边形划分成不同的两部分和一个三角形。
联想矩阵链的递推方程：将其划分成两个不同的子链+这两个自链所构成的矩阵乘法次数

相同点：两种思路一致，
不同点：矩阵连计算次数是 pi-1 * pK* pj
多变形是三边之和

4.关于递推方程：t[i][j] = t[i][k] + t[k+1][j] + w(i-1,k,j);
这里需要说明的是t[i][j]即表示的是多边形的剖分最小权值和（所有三角形的）
比如t[1][6] = t[1][1] + t[2][6] + w(0,1,6), (7个顶点)
通过点0，1，6将多边形剖分成三部分
其中t[1][1] = 0(三角剖分中只有一条边的是不可以被剖分成多边形的故其权值和为0)
t[2][6] 表示的是剩下的多变形，然后再求取它的最小值

通过这样的分析：我们可以得知 t[2][6],也就相当于矩阵连相乘问题中的
子链，那么我就还是可以通过建网格来存储每个多边形的最小权值和
来进行求解
5.本题题解：
通过上述分析我们可以得出：
求取凸多边形最优三角剖分 = t[1][n - 1];
6：这里有一张图是将矩阵链中的矩阵映射在凸多变形的边上，方便兄弟们更容易理解算法
7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby！！！！！！！！！

四：上码：

/**
	分析： 
	1.凸多边形的三角剖分是将凸多边形分割成互不相交的三角
	  形的弦的集合。
	2.最优三角剖分中诸三角形上权值和：指的是将多边形划分成多个三角形
	                                  其所有的三角形的周长和最小
	3.和矩阵连相乘的思路比较：凸三角形的剖分是通过一个三角形将多边形划分成不同的两部分
							和一个三角形。
		联想矩阵链的递推方程：将其划分成两个不同的子链+这两个自链所构成的矩阵乘法次数
		
		相同点：两种思路一致，
		 不同点：矩阵连计算次数是 pi-1 * pK* pj 
				 多变形是 三边之和	
				 
	4.关于递推方程：t[i][j] = t[i][k] + t[k+1][j] + w(i-1,k,j);
	   这里需要说明的是t[i][j]即表示的是多边形的剖分最小权值和（所有三角形的）
	   比如t[1][6] = t[1][1] + t[2][6] + w(0,1,6),
	   通过点0，1，6将多边形剖分成三部分
	   其中t[1][1] = 0(三角剖分中 只有一条边的是不可以 被剖分成  多边形的 故其权值和为0)
	       t[2][6] 表示的是剩下的多变形，然后再求取它的最小值
	  
	  通过这样的分析：我们可以得知 t[2][6],也就相当于矩阵连相乘问题中的
	  				  子链，那么我就还是可以通过建网格来存储每个多边形的最小权值和
					  来进行求解
	5.本题题解：
	   通过上述分析我们可以得出： 
	  求取凸多边形最优三角剖分 = t[1][n]; 
	 				  			   						  
*/ 

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

int array1[200][200];

//剖分三角形的周长 
int C_triangle(int i,int k,int j){
	return array1[i][k] + array1[k][j] + array1[i][j];
} 

int main(){
	
	int N;
	cin >> N;
	int m[200][200];
	
	//比如有7个顶点（v0,v1..v6）,我们数组中存的是边长和弦长 
	for(int i = 0; i < N; i++){
		for(int j  = i; j < N; j++){
			cin >> array1[i][j];
		}
	}
	
//	for(int i = 1; i <= N; i++){
//		for(int j  = 1; j <= N; j++){
//			cout <<  array[i][j] << ' ';
//		}
//		cout << endl;
//	}
	
	for(int i = 0; i <= N; i++){
		m[i][i] = 0;
	}
		
	//开始划分网格和更新
     	
	for(int i = N - 1; i >= 1; i--){
		for(int j = i+1; j <= N - 1; j++){//这里j从i+1开始，因为从i开始每次m[i][i] = 0; 这里j <= N 表示的是这一行到最后比如m[i][N] 
		
			//初始化二维数组 
			m[i][j] = m[i][i] + m[i+1][j] + C_triangle(i-1,i,j);
			
			for(int k = i+1; k < j; k++){
				int temp = m[i][k] + m[k+1][j] + C_triangle(i-1,k,j);
				
				if(temp < m[i][j]){
					 m[i][j] = temp;
				} 
			} 
		}
	} 
	
	
//	for(int i = 1; i < N; i++){
//		for(int j = 1; j < N; j++){
//			cout << m[i][j] << ' ';
//		}
//		cout << endl; 
//	}
	
//	cout << C_triangle(4,5,6); 
	
	cout << m[1][N-1];
	
}