不愧是蓝题,方程转移和单调队列难想。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
long double sx,sy,a[200010],b[200010],s1[200010],s2[200010],f[200010];
ll n,k,q[200010];
int main()
{
	scanf("%lld%lld%Lf%Lf",&n,&k,&sx,&sy);
	for(ll i=1;i<=n;i++)scanf("%Lf%Lf",&a[i],&b[i]);
	for(ll i=1;i<=n;i++)s1[i]=sqrtl(pow(a[i]-sx,2)+pow(b[i]-sy,2));//计算距离公式 
	for(ll i=2;i<=n;i++)s2[i]=s2[i-1]+sqrtl(pow(a[i]-a[i-1],2)+pow(b[i]-b[i-1],2));//距离的前缀和,因为老人想按顺序送礼物 
	for(ll i=1;i<=n;i++)f[i]=1e16;//求最小,先最大
	ll l=1,r=0;
	for(ll i=1;i<=n;i++)//单调队列:一次送出礼物数,最值只与它有关 
	{
		while(l<=r&&f[q[r]]+s1[q[r]+1]-s2[q[r]+1]>=f[i-1]+s1[i]-s2[i])r--;//保证队列为升序
		q[++r]=i-1;
		while(l<=r&&q[l]+k<i)l++;//超出限制让队头出队,尽量保证最值 
		f[i]=min(f[i],f[q[l]]+s1[q[l]+1]+s1[i]+s2[i]-s2[q[l]+1]);//方程转移
	}
	printf("%.15Lf",f[n]);//结束
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
#define PII pair<int,int>
#define fi first
#define se second
double dis(PII n1,PII n2){return sqrt((n1.fi-n2.fi)*(n1.fi-n2.fi)+(n1.se-n2.se)*(n1.se-n2.se));}
PII p[N];double a[N],d[N],d2[N],dp[N];
signed main()
{
	int n,k,stx,sty;cin>>n>>k>>stx>>sty;
	for(int i=1;i<=n;i++)cin>>p[i].fi>>p[i].se;
	for(int i=1;i<n;i++)d[i]=dis(p[i],p[i+1]);
	for(int i=1;i<=n;i++)d2[i]=dis(p[i],{stx,sty});
	for(int i=1;i<n;i++)a[i]=d2[i]+d2[i+1]-d[i];
	deque<pair<double,int>>q;
	q.push_back({0,0});
	for(int i=1;i<n;i++)
	{
		while(!q.empty()&&i-q.front().second>k)q.pop_front();
		dp[i]=(q.empty()?0:q.front().first)+a[i];
		while(!q.empty()&&q.back().first>=dp[i])q.pop_back();
		q.push_back({dp[i],i});
	}
	double anss=1e18;for(int i=n-k;i<n;i++)anss=min(anss,dp[i]);
	double ans=d2[1]+d2[n]+anss;
	for(int i=1;i<n;i++)ans+=d[i];
	printf("%.10lf",ans);
	return 0;
}