专栏文章

题解：P7823 「RdOI R3」闹钟

SStaque
P7823题解参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@minlngnw
此快照首次捕获于
2025/12/02 04:26
3 个月前
此快照最后确认于
2025/12/02 04:26
3 个月前
查看原文
线段树优化动态规划板题。
一开始肯定不会想到线段树，首先设状态，设 dpi,jdp_{i,j} 为时间 ii，自由的闹钟在 jj 位置时的最小花费。
转移有两种。
第一种是由上一个时间点的自由闹钟完成这一时间点的任务，则这一个时间点的自由闹钟一定是前一个的任务闹钟，有转移：
dpi,ki−1=max⁡(dpi−1,j+∣j−ki∣)dp_{i,k_{i-1}}=\max (dp_{i-1,j}+\left|j-k_i\right|)
第二种是由上一个时间点的任务闹钟完成这一时间点的任务，则这一个时间点的自由闹钟一定还是前一个的自由闹钟，有转移：
dpi,j=dpi−1,j+∣ki−ki−1∣dp_{i,j}=dp_{i-1,j}+\left| k_i-k_{i-1} \right|
发现 dpi,jdp_{i,j} 转移只与 dpi−1dp_{i-1} 有关，所以可以滚掉一维。
考虑把第一个式子的绝对值拆开。
dpi,ki−1=max⁡(dpi−1,j−j+ki),j≤kidp_{i,k_{i-1}}=\max (dp_{i-1,j}-j+k_i),j\leq k_i
dpi,ki−1=max⁡(dpi−1,j+j−ki),ki<jdp_{i,k_{i-1}}=\max (dp_{i-1,j}+j-k_i),k_i<j
这个时候我们就可以分别维护 dpi,j−jdp_{i,j}-j 和 dpi,j+jdp_{i,j}+j，发现转移实际上就是支持区间查询最小值、单点修改和全局加，这个东西可以使用线段树轻松实现。
发现位置的值域很大，因此离散化预处理即可。
时间复杂度 O(nlog⁡n)O(n\log n)。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll inf=1e18;
int n,m,a[N];
ll cl[N],cr[N],b[N];
ll ABS(int x){return x>0?x:-x;}
namespace seg{
  int L[N<<2],R[N<<2];
  ll tg[N<<2],vl[N<<2],vr[N<<2];
  void pushup(int u){
    vl[u]=min(vl[u<<1],vl[u<<1|1]);
    vr[u]=min(vr[u<<1],vr[u<<1|1]);
  }
  void pushtag(int u,ll x){vl[u]+=x,vr[u]+=x,tg[u]+=x;}
  void pushdown(int u){
    if(!tg[u])return ;
    pushtag(u<<1,tg[u]),pushtag(u<<1|1,tg[u]);
    tg[u]=0;
  }
  void build(int u,int l,int r){
    L[u]=l,R[u]=r;
    if(l==r){vl[u]=cl[l],vr[u]=cr[l];return ;}
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
  }
  ll qryl(int u,int l,int r){
    if(l>r)return inf;
    if(L[u]>=l&&R[u]<=r)return vl[u];
    ll res=inf;int mid=L[u]+R[u]>>1;
    pushdown(u);
    if(l<=mid)res=qryl(u<<1,l,r);
    if(r>mid)res=min(res,qryl(u<<1|1,l,r));
    return res;
  }
  ll qryr(int u,int l,int r){
    if(l>r)return inf;
    if(L[u]>=l&&R[u]<=r)return vr[u];
    ll res=inf;int mid=L[u]+R[u]>>1;
    pushdown(u);
    if(l<=mid)res=qryr(u<<1,l,r);
    if(r>mid)res=min(res,qryr(u<<1|1,l,r));
    return res;
  }
  void update(int u,int x,ll v){
    if(L[u]==R[u]){
      vl[u]=min(vl[u],v-b[x]);
      vr[u]=min(vr[u],v+b[x]);
      return ;
    }int mid=L[u]+R[u]>>1;
    pushdown(u);
    if(x<=mid)update(u<<1,x,v);
    else update(u<<1|1,x,v);
    pushup(u);
  }
  void add(ll x){pushtag(1,x);}
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];b[n+1]=0;
  if(n==1){cout<<a[1];return 0;}
  sort(b+1,b+1+n+1);
  m=unique(b+1,b+1+n+1)-b-1;
  for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+m,a[i])-b;
  for(int i=1;i<=m;i++){
    cl[i]=b[a[1]];
    cr[i]=b[a[1]]+b[i]+b[i];
  }
  seg::build(1,1,m);
  for(int i=2;i<=n;i++){
    int nw=ABS(b[a[i]]-b[a[i-1]]);
    seg::add(nw);
    ll p=seg::qryl(1,1,a[i])-nw;
    seg::update(1,a[i-1],p+b[a[i]]);
    p=seg::qryr(1,a[i]+1,m)-nw;
    seg::update(1,a[i-1],p-b[a[i]]);
  }
  ll ans=inf;
  for(int i=1;i<=m;i++)ans=min(seg::qryl(1,i,i)+b[i],ans);
  cout<<ans;
  return 0;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...