ABC 315F Shortcuts

题意
有N个点，你从第一个点出发，要按顺序经过所有的点，最终抵达第N个点。在这个过程中你可以跳过一些点，但如果你跳过了C个点，那么你必须要接受pow(2,C-1)的惩罚。设s为你走过的距离加上你的惩罚，请求出最小化s。

题解
显然考虑dp，设计dp[i][j]为到达第i个点，中途跳过了j个点需要的路程。考虑到跳过惩罚为指数函数，那么跳跃的点一定不会太多，那么这样我们可以枚举j<=30即可。在状态转移的过程中我们考虑。当到达dp[i][j]时，我们要枚举的东西是：

1. 第i个点由哪一个点j跳跃过来(max(1,i-30)<=j<i)
2. 枚举已经跳跃的步数（注意，是“已经跳跃的步数”，因为从j跳跃到i是必然会跳一次的，所以我们要枚举的是已经跳跃的点），剩下的就是注意细节就行了，具体实现看代码

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e4+10;
double dp[maxn][100]; 

struct node
{
	int x,y;
}a[maxn];

double dis(node x,node y) 
{
   return sqrt(1.0*(x.x-y.x)*(x.x-y.x)+1.0*(x.y-y.y)*(x.y-y.y));
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin>>n;
	const int mo=1;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	for(int i=1;i<=n;i++) for(int j=0;j<=30;j++) dp[i][j]=1e18;
	dp[1][0]=0;
	for(int i=2;i<=n;i++)//更新dp[i][j]，表示到达第i个点跳跃j个点需要的路程 
	{
		for(int j=max(mo,i-30);j<=i-1;j++)//枚举跳跃点 
		{
			for(int k=0;k<=min(mo*30,i-1);k++)//枚举跳跃的步数 
			{
				if(k-(i-j)+1<0) continue;
				dp[i][k]=min(dp[i][k],dp[j][k-i+j+1]+dis(a[i],a[j]));
			}
		}
	}
	double ans=dp[n][0];
	int p=1;
	for(int i=1;i<=30;i++)
	{
		ans=min(ans,dp[n][i]+pow(2,i-1));
		p=p*2;
	}
	printf("%.7f",ans);
	
	return 0;
 }