2024 CCPC Liaoning Provincial Contest D

补题链接

看似解析几何实则DP，$\sout{被诈骗了}$,题目是说每次选择前面的所有未选择的点用最小的凸多边形覆盖，可以在二维平面平动和转动，问$y$轴累加最高多少,选择两个点会退化成线段，那么显然每次选择两个点更好,题目就变成了，n个点划分成若干线段，线段和 $max$ 是多少,显然DP $dp[i]=ma{x}_{j=1}^i(dp[j-1]+dis(p_i,p_j))$ $p_i$ ,$p_j$是两个点

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 5012;

array<i64,2> p[maxn];
long double dp[maxn];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>p[i][0]>>p[i][1];
    }
    auto dis=[&](int x,int y)->long double{
        return sqrtl((p[x][0]-p[y][0])*(p[x][0]-p[y][0])+(p[x][1]-p[y][1])*(p[x][1]-p[y][1]));
    };
    for(int i = 1;i<=n;++i){
        for(int j = 1;j<=i;++j){
            dp[i] = max(dp[i],dp[j-1]+dis(j,i));
        }
    }
    cout<<fixed<<setprecision(10)<<dp[n]<<"\n";
    return 0;
}