题解：P11491 [BalticOI 2023] Tycho

_Ch1F4N_ · 2025-06-06 10:47:58 · 题解

你思考下我们到底在干嘛。

我们希望尽快走到终点，并且为了避免惩罚，需要在中途一些形如 k \times p 的时刻踩在关键点上。

并且对于一个关键点，假若用其规避了 k \times p 时刻的惩罚，就没必要用其规避 (k+1) \times p 时刻的惩罚，因为对规避后面的惩罚无收益还浪费时间。

所以实际上我们只关心哪些关键点作为了规避惩罚的点，于是有一个 O(n^2) 的 dp。

这个 dp 最难处理的项是 i 转移到 j 时有一个 a_j-a_i 除以 p 上取整，讨论 a_j \bmod p,a_i \bmod p 的大小关系后可以拆成 a_j/p 下取整，a_i/p 下取整之差并且可能需要再加上 1，动态开点线段树维护 a_k \bmod p = i 的最优决策即可做到 O(n \log p)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define lowbit(x) (x&(-x))
const int maxn = 1e5+114;
int a[maxn],n,b,p,d;
int dp[maxn];
int tr[maxn*60],ls[maxn*60],rs[maxn*60],tot;
int root;
void upd(int &cur,int lt,int rt,int pos,int v){
    if(cur==0){
        cur=++tot;
        tr[cur]=1e18;
    }
    tr[cur]=min(tr[cur],v);
    if(lt==rt) return ;
    int mid=(lt+rt)>>1;
    if(pos<=mid) upd(ls[cur],lt,mid,pos,v);
    else upd(rs[cur],mid+1,rt,pos,v);
}
int ask(int cur,int lt,int rt,int l,int r){
    if(cur==0) return 1e18;
    if(r<lt||rt<l) return 1e18;
    if(l<=lt&&rt<=r) return tr[cur];
    int mid=(lt+rt)>>1;
    return min(ask(ls[cur],lt,mid,l,r),ask(rs[cur],mid+1,rt,l,r));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>b>>p>>d>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=n;i++) dp[i]=1e18;
    dp[0]=0;
    upd(root,0,p-1,0,dp[0]);
    int ans=b+(b-1)/p*d;
    for(int i=1;i<=n;i++){
        dp[i]=min(dp[i],ask(root,0,p-1,0,p-1)+(a[i]/p+1)*(p+d));
        dp[i]=min(dp[i],ask(root,0,p-1,a[i]%p,p-1)+a[i]/p*(p+d));
        dp[i]-=d;
        upd(root,0,p-1,a[i]%p,dp[i]-(a[i]/p)*(p+d));
        int dist=(b-a[i]);
        ans=min(ans,dp[i]+dist+(dist-1)/p*d);
    }
    cout<<ans<<"\n";
    return 0;
}