7-1 凸多边形最优三角剖分
用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。
给定凸多边形P，用互不相交的弦将P分为一个个的三角形,称为凸多边形三角剖分。
然后，定义多边形的边和弦组成的三角形上的权w（本题定义三角形的权为边长之和）。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小，则称其为凸多边形P的最优三角剖分。
输入格式:
第一行一个n,表示有n个顶点（n<20）。
接下来n行，每行两个小数，分别表示该点的横坐标和纵坐标。
输出格式:
一个小数，表示最优三角剖分后，所有三角形的边长和的和最小值，小数点后保留2位。
输入样例:
4
1.0 1.0
4.0 1.0
4.0 5.0
1.0 5.0
输出样例:
24.00
注意到多边形里面的边对答案的贡献会计算两次，而多边形边上的边只计算一次。设dp[i][j]为i到j构成的多边形剖分后每条边只计算一次的答案，sum_b为多变行边的总长度，那么最终的答案为(dp[1][n]-sum_b)*2+sum_b
区间dp,分成i-k和k+1到j两段，计算把这两端合起来需要的代价，注意当k+1到j的长度为1时需要特殊处理。
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+dis(t[i],t[j])+dis(t[k],t[k+1])+min(dis(t[i],t[k+1]),dis(t[j],t[k])));
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yesno if(fg)yes;else no;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=1e9;
const int maxn=100;
struct node
{
double x,y;
}t[maxn];
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double dp[maxn][maxn];
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t[i].x>>t[i].y;
//t[i+n].x=t[i].x;
//t[i+n].y=t[i].y;
}
for(int i=0;i<maxn;i++)
for(int j=0;j<i;j++)
dp[j][i]=inf;
double sum_b=dis(t[1],t[n]);
for(int i=1;i<n;i++)sum_b+=dis(t[i],t[i+1]);
//n=n*2;
for(int i=1;i<n;i++)
{
dp[i][i+1]=dis(t[i],t[i+1]);
}
for(int len=3;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
dp[i][j]=min(dp[i][j],dp[i][j-1]+dis(t[i],t[j])+dis(t[j-1],t[j]));
dp[i][j]=min(dp[i][j],dp[i+1][j]+dis(t[i],t[j])+dis(t[i],t[i+1]));
for(int k=i+1;k<=j-1;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+dis(t[i],t[j])+dis(t[k],t[k+1])+min(dis(t[i],t[k+1]),dis(t[j],t[k])));
}
//dp[i][j]=min(dp[i][j],dp[i][j-1]+dis(t[i],t[j]));
//dp[i][j]=min(dp[i][j],dp[i+1][j]+dis(t[i],t[j]));
}
}
double ans=dp[1][n];
printf("%.2lf",(ans-sum_b)*2+sum_b);
}
/*
5
1.0 1.0
4.0 1.0
4.0 5.0
1.0 5.0
0 3
*/
原文地址：https://blog.csdn.net/qq_51737737/article/details/143601338
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！