一.问题描述
【问题描述】使用动态规划算法解凸多边形最优三角剖分问题，具体来说就是，依据递归式，按照顺序求得子问题，使得该三角剖分中诸三角形上权之和为最小。
【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。
【输出形式】最优三角剖分后的三角形顶点。
【样例1输入】
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
【样例2输出】
012
234
024
456
046
二.思路
三.代码

#include<bits/stdc++.h>
using namespace std;
int t[50][50],s[50][50];
int arrx[50],arry[50];
int calweight(int a,int b,int c);
void MIN_WEIGHT_TRIANGULATION(int n){
	int j;
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			j=i+len-1;
			t[i][j]=0xFFFFFFF;
			for(int k=i;k<=j-1;k++){
				int q=t[i][k]+t[k+1][j]+calweight(i-1,k,j);
				if(q<t[i][j]){
					t[i][j]=q;
					s[i][j]=k;
				}
			}
		}
	}
}

void print(int i,int j){
	if(i==j)
		return;
	print(i,s[i][j]);
	print(s[i][j]+1,j);
	cout<<i-1<<s[i][j]<<j<<endl;
} 
int calweight(int a,int b,int c){
	int x=sqrt(pow(arrx[a]-arrx[b],2)+pow(arry[a]-arry[b],2));
	int y=sqrt(pow(arrx[a]-arrx[c],2)+pow(arry[a]-arry[c],2));
	int z=sqrt(pow(arrx[b]-arrx[c],2)+pow(arry[b]-arry[c],2));
	return x+y+z;
}
int main(){
	int cnt;
	cin>>cnt;
	for(int i=0;i<cnt;i++){
		cin>>arrx[i]>>arry[i];
	}
	cnt--;
	MIN_WEIGHT_TRIANGULATION(cnt);
	print(1,cnt); 

}
/*
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
*/