スキップした頂点が多いほどペナルティが大きくなる． スキップできる箇所はそんなに多くないのがポイント．
スキップしないで頂点を通った場合，最大で \(2^{1/2} 10^{4}*n \leq 1.5 \cdot 10^{8}\). ペナルティがこれよりも大きい場合，ペナルティを受けるほうが確実に損をするので調べる必要がない． \(2^{c-1} \geq 10^{8}\) となる \(c\) は調べる必要がない．
\(i \in n\) と \(j \leq min(30,i+1)\) に対して，
\(dp_{i,j} := \) \([0,i]\) まで頂点を調べて，最後に \(i\) で止まっていて， \([0,i]\) の中から \(j\) 個の頂点をスキップしたときの min distance.
とおく．
遷移を考える． 例えば，頂点\([0,3]\) までスキップするか通るか決めていて，今は頂点3に居るとする． 頂点 2 をスキップしているとする． 次に遷移するべき点は，
- 頂点4: スキップは 2の 1つ
- 頂点5: スキップは 2,4の 2つ
- 頂点6: スキップは 2,4,5の 3つ
の様になる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INFL = 1LL << 60;
using pll = pair<ll,ll>;
#define srep(i,s,t) for (ll i = (s); i < (t); ++i)
#define rep(i,n) srep(i,0,(n))
#define dsrep(i,t,s) for(ll i = (t)-1; i >= (s); --i)
#define drep(i,n) dreprng(i,0,(n))
#define drep1(i,n) dreprng(i,1,(n+1))
#define fore(i,a) for(auto &i:(a))
#define forit(i,a) for(auto i = (a).begin(); i != (a).end(); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<typename T> bool in(T x, T l, T r){
if(l >= r) return false;
return l <= x && x < r;
}
template<typename T> bool in(T x, T a){ return in(x, (T)0, a); }
template<typename T> bool in(T x, T l, T r){
if(l >= r) return false;
return l <= x && x < r;
}
template<typename T> bool in(T x, T a){ return in(x, (T)0, a); }
template<typename T> bool in(T x, set<T> &s){ return s.find(x) != s.end(); }
fore(i, v){ if(i == x) return true; }
return false;
}
// @ debug
template<typename T> bool in(char x, string &v){
fore(i, v){ if(i == x) return true; }
return false;
}
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; }
#define pcntll __builtin_popcountll
template<typename T>void uni(T& a){sort(rng(a));a.erase(unique(rng(a)),a.end());}
#define drep1(i,n) dreprng(i,1,(n+1))
rep(i, m.size()){
rep(j, m[i].size()){
cin >> m[i][j];
}
}
}
void yesno(bool f){ if(f){ cout << "Yes" << endl; } else{ cout << "No" << endl; } }
int main() {
ll n;
cin >> n;
vll x(n), y(n);
rep(i,n){
cin >> x[i] >> y[i];
}
auto dis = [&](ll i, ll j) -> double {
ll dx = x[i]-x[j];
ll dy = y[i]-y[j];
return sqrt(dx*dx + dy*dy);
};
// [0,i] まで調べて
// j 個スキップ
// とくに j <= i が必要
const ll m = 30;
dp[0][0] = 0;
rep(i,n) rep(j,m) {
for(ll ni=i+1, nj=j; ni<n && nj<m; ni++, nj++){
if(j<=i) // 無くても AC
chmin(dp[ni][nj], dp[i][j]+dis(i,ni));
}
}
double ans = INFL;
rep(j,m) chmin(ans, dp[n-1][j] + (1LL<<j>>1LL)); // j = 0 のとき，ペナルティが 0
printf("%.10lf\n",ans);
return 0;
}
#define drep(i,n) dreprng(i,0,(n
