题目要求：用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。 给定凸多边形P，用互不相交的弦将P分为一个个的三角形,称为凸多边形三角剖分。 然后，定义多边形的边和弦组成的三角形上的权w（本题定义三角形的权为边长之和）。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小，则称其为凸多边形P的最优三角剖分。 输入格式: 第一行一个n,表示有n个顶点（n<20）。 接下来n行，每行两个小数，分别表示该点的横坐标和纵坐标。 输出格式: 一个小数，表示最优三角剖分后，所有三角形的边长和的和最小值，小数点后保留2位。 用c++实现

以下是使用 C++ 实现的凸多边形最优三角剖分算法：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 20;

int n;
double x[N], y[N];
double dp[N][N];

double dis(int i, int j, int k)
{
    double a = x[i] - x[k], b = y[i] - y[k];
    double c = x[j] - x[k], d = y[j] - y[k];
    return sqrt(a * a + b * b) + sqrt(c * c + d * d);
}

double solve(int i, int j)
{
    if (j - i <= 1) return 0;
    if (dp[i][j] >= 0) return dp[i][j];
    double res = 1e20;
    for (int k = i + 1; k < j; k++)
        res = min(res, solve(i, k) + solve(k, j) + dis(i, j, k));
    return dp[i][j] = res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    memset(dp, -1, sizeof dp);
    double ans = solve(0, n - 1);
    printf("%.2lf\n", ans);
    return 0;
}

这个算法使用了递归和记忆化搜索的方法，时间复杂度为 O(n^3)。我们可以通过记忆化搜索来避免重复计算，从而提高算法的效率。具体来说，我们可以定义一个二维数组 dp[i][j]，表示从点 i 到点 j 的最优三角剖分的权值和。递归地计算 dp[i][j]，如果 dp[i][j] 已经计算过了，那么直接返回 dp[i][j]。如果 i 和 j 之间只有两个点，那么它们之间的边就是一条弦，权值就是 i、j 和它们之间的点的距离。如果 i 和 j 之间有三个或以上的点，那么可以枚举它们之间的任意一条弦 k，把凸多边形分成两个部分：i、k 和它们之间的点组成的凸多边形和 k、j 和它们之间的点组成的凸多边形。然后，递归地计算出这两个部分的最优三角剖分的权值和，再加上 i、j 和 k 之间的距离就可以得到 dp[i][j] 的值。最终的答案就是 dp[0][n-1]，其中 n 是凸多边形的顶点数。