例えば、 \(100\) 個のチェックポイントを無視したとしましょう。

この時 \(2^{99} \approx 10^{30}\) のペナルティが発生しますが、愚直に全てのチェックポイントを回ったとしても距離の総和は \(N \times 10^5\) 以内で収まるので、この数の無視をするのは明らかに無駄であることが分かります。

この時、以下の DP が成立します:
dp[最後に通ったチェックポイント][無視したチェックポイントの数] = {距離の総和の最小値}
二つ目の添字 は \(100\) 未満しか考慮しなくて良いことに注意してください。

\(dp[1][0]=0\) 、その他のテーブルの値は \(\infty\) に初期化され、答えは 「 \(dp[N][i]\) に \(i\) 個のチェックポイントを無視した際のペナルティを足したもの」の最小値となります。

このことから、考慮する無視の回数の上限を \(C\) としたとき、時間計算量 \(O(NC^2)\) でこの問題に正解できます。 ( \(C=100\) とするとギリギリになる可能性がありますが、もう少しよい見積をすると実行時間に余裕を持って AC できます。 )

実装例 (C++):

#include<bits/stdc++.h>
 
using namespace std;
using pi=pair<int,int>;
 
long double dist(pi a,pi b){
  int dx=a.first-b.first;
  int dy=a.second-b.second;
  int ss=dx*dx+dy*dy;
  return sqrt((long double)ss);
}
 
long double lg=8.0e18;
 
int main(){
  int n;
  cin >> n;
  vector<pi> vp(n);
  for(int i=0;i<n;i++){
    cin >> vp[i].first >> vp[i].second;
  }
 
  vector<vector<long double>> dp(n,vector<long double>(60,lg));
  dp[0][0]=0.0;
  for(int i=1;i<n;i++){
    for(int j=i-1;j>=0;j--){
      int skip=i-j-1;
      for(int k=0;(k+skip)<60;k++){
        dp[i][k+skip]=min(dp[i][k+skip],dp[j][k]+dist(vp[j],vp[i]));
      }
    }
  }
 
  long double res=lg;
  for(int i=0;i<60;i++){
    long double pen=0.0;
    if(i>0){
      pen=pow(2.0,(long double)(i-1));
    }
    res=min(res,dp[n-1][i]+pen);
  }
 
  printf("%.6Lf\n",res);
  return 0;
}