AT_abc334_f 讲解

zrl123456 · 2023-12-29 18:28:19 · 题解

这道题大部分都是使用 dp 和单调队列去做的， 中间也需要前缀和来维护， 题解中也有一些讲解。
只是做的时候要注意是按 1 到 N 的顺序送礼物就可以了。

非正解

这里我们设圣诞老人家为 0 号房间， sum_i 为圣诞老人从 0 号房间到 1 号房间， 再到 2 号， 3 号...... 直到 i 号且中途不回自己家的距离，m(i,j) 表示 i 号房间到 j 号房间的欧几里得距离， 下文公式中的 i 表示圣诞老人所在的房间， j 表示圣诞老人在送完 i-j 号房间后回到自己家中。
易得公式：

将与 j 不相关的项移出函数， 得：

所以我们只需枚举出 f_{i-j}+m(i-j+1,0)-sum_{i-j+1} 的最小值即可。
时间复杂度为 O(n^2)， 明显超时。

正解

分析代码， 发现明显可以使用单调队列优化。
那么存入单调队列中的下标固然为 i， 值应将 j 移出， 得 f_i+m(i+1,0)-sum_{i+1}， 我们用 ans(i) 表示 。
那么我们设队首下标为 l， 则公式得：

那如何处理队列为空的情况呢？
很简单， 在队列中放入一个 0 即可。
时间复杂度为 O(n)。
代码：

#include<bits/stdc++.h>
#define m(i,j) sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
#define ans(i) f[i]+m(i+1,0)-sum[i+1]
using namespace std;
deque<int>d;
const int MAX=2*1e5+5;
long long n,k,x[MAX],y[MAX];
double sum[MAX],f[MAX];
void que(int l){
    while(!d.empty()&&d.front()+k<=l) d.pop_front();
    while(!d.empty()&&ans(d.back())>ans(l)) d.pop_back();
    d.push_back(l);
    return; 
} 
int main(){
    cin>>n>>k;
    for(int i=0;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+m(i,i-1);
    d.push_back(0);
    for(int i=1;i<=n;i++){
        f[i]=ans(d.front())+m(i,0)+sum[i];
        que(i);
    }
    printf("%.15lf",f[n]);
    return 0;
}