《关于kevin并没有详细解答为何最多跳过$31$个点这件事》

特此来解释一手

如果说他跳了多余$31$个点，比如$32$个点，那他的惩罚就是$1,073,741,824$，还不如直接老老实实的走，反正直接按顺序走最多也就$141,421,356$的距离（每一次走都在$0$~$1e4$之间来回走动），你何必呢？

PS:事实验证，跳过$25$个点就可以AC了。

试着分析一下为什么惩罚不是 $C^2$ 而是 $2^{C-1}$？

因为这样就预示着你最多跳过 $31$ 个点。

剩下的就不说了吧。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],b[N];double dp[N][35];
double dis(int x,int y){return sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	for(int i=1;i<=n;i++)for(int j=0;j<=31;j++)dp[i][j]=2e9;
	dp[1][0]=0;
	for(int i=1;i<=n;i++)for(int j=0;j<=31;j++)for(int k=1;i+k<=n&&j+k-1<=31;k++)
		dp[i+k][j+k-1]=min(dp[i+k][j+k-1],dp[i][j]+dis(i,i+k));
	double ans=dp[n][0];
	for(int i=1;i<=31;i++)ans=min(ans,dp[n][i]+(1<<i-1));
	printf("%.10lf",ans);
	return 0;
}