ABC334F 单调队列优化DP RE #4求调
查看原帖
ABC334F 单调队列优化DP RE #4求调
242317
xiaofu15191楼主2024/1/18 20:23
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,k,d[100010];
long double santa[2],dis_to_santa[200010],sum[200010],x[200010],y[200010],f[200010];
long double distance(long double x1,long double y1,long double x2,long double y2)
{
	return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%Lf%Lf",&santa[0],&santa[1]);
	for(int i=1;i<=n;i++)
	{
		scanf("%Lf%Lf",&x[i],&y[i]);
		dis_to_santa[i]=distance(x[i],y[i],santa[0],santa[1]);
		sum[i]=sum[i-1]+distance(x[i],y[i],x[i-1],y[i-1]);
	}
	int head=1,tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<=tail&&f[d[tail]]+dis_to_santa[d[tail]+1]-sum[d[tail]+1]>f[i-1]+dis_to_santa[i]-sum[i]) tail--;
		d[++tail]=i-1;
		while(head<=tail&&d[head]+k<i) head++;
		f[i]=f[d[head]]+dis_to_santa[d[head]+1]+dis_to_santa[i]+sum[i]-sum[d[head]+1];
	}
	printf("%.8Lf\n",f[n]);
}
2024/1/18 20:23
加载中...