Codeforces 838E. Convex Countour

题意：

给你一个凸多边形，你要找到一个最长的不相交的路径，并且每个顶点最多经过一次。

题解：

首先要知道，最优方案一定是每个点都经过一次的。然后倍长一下，f[l][r][0/1]表示走完了l ~ r的所有点，现在再l/r的最长路径。转移看一下从哪边走过来就好了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
struct pnt
{
    double x, y;
} a[5010];
double f[2510][5010][2];

double dis(pnt x, pnt y)
{
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &a[i].x, &a[i].y);
        a[i + n] = a[i];
    }
    for (int i = 1; i < n; i++)
    {
        for (int l = 1; l <= n; l++)
        {
            int r = l + i;
            f[l][r][0] = max(f[l + 1][r][0] + dis(a[l + 1], a[l]), f[l + 1][r][1] + dis(a[r], a[l]));
            f[l][r][1] = max(f[l][r - 1][0] + dis(a[l], a[r]), f[l][r - 1][1] + dis(a[r - 1], a[r]));
        }
    }
    double ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max({ans, f[i][i + n - 1][0], f[i][i + n - 1][1]});
    printf("%.12lf\n", ans);
}