ABC315F 解题报告
题意：给定 \(n\) 个点在平面上的位置，你需要从 \(1\) 号点走到 \(n\) 号点，两点间距离为欧几里得距离，你可以走的过程中你可以跳过某些点（即不用到达这个点）直接跳到下一个点，记你总共有 \(k\) 个点选择跳过，那么总答案要加上 \(2^{k-1}\)，若 \(k=0\) 则不用加。最小化总的欧几里得距离和额外答案之和。\(1 \le n \le 10^4\)，值域 \(1 \le x_{i},y_{i} \le 10^4\)。
这看第一眼很 dp 啊。
首先指数增长趋势非常快，题目又没要求取模，我们需要先考虑 \(k\) 的大致范围。
假设我们全都不跳过，额外惩罚为 \(0\)，那么最大欧几里得距离即不断在地图两个边界跳，最大可能为 \(\sqrt{(10^8+10^8)} \times n\)，大概也就 \(10^8\) 左右，那你的 \(k\) 一旦超过 \(\log(10^8)\) 必然不优。我们 \(k\) 上界取到 \(40\) 也无所谓。
那么就可以直接上 dp 了，由于我是 dp 菜狗所以写了记搜。设 \(f_{i,j}\) 表示跳到第 \(i-1\) 个点一共跳过了 \(j\) 个点的最小代价，\(\mathrm{dist}(i,j)\) 表示 \(i\) 点和 \(j\) 点的欧几里得距离。则有转移：
\[f_{k,j}=\min_{i=1}^{\min{(n-k,30)}} \mathrm{dfs}(i+k,j+i-1)+\mathrm{dist}(k,i+k)
\]
是不是这样写公式啊（逃
当跳过的点数超过了限制记得及时剪枝，设钦定的剪枝边界为 \(V\)，那么总复杂度为 \(O(nV^2)\)，可以通过。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n,m,i,j;
long double dis[N],a[N],b[N],ans=1000000000.00,qp[65],f[N][65];
long double solve(int x,int y){
return sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));
}
long double dfs(int k,int cnt){
if(k==n){
if(cnt==0) return 0.0;
return qp[cnt-1];
}
if(f[k][cnt]!=-1.0) return f[k][cnt];
long double Mx=1000000000000000.0;
for(int i=1;i+k<=n;i++){
if(cnt+(i-1)>30) break;
Mx=min(Mx,dfs(i+k,cnt+i-1)+solve(k,k+i));
}
return f[k][cnt]=Mx;
}
int main(){
qp[0]=1.0;for(i=1;i<=60;i++) qp[i]=qp[i-1]*2.0;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%Lf%Lf",&a[i],&b[i]);
for(i=1;i<=n;i++){
for(j=0;j<=60;j++) f[i][j]=-1.0;
}
ans=dfs(1,0);
printf("%.20Lf",ans);
return 0;
}