例えば、 $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;
}

#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;
}