题解：P7823 「RdOI R3」闹钟

· · 题解

线段树优化动态规划板题。

一开始肯定不会想到线段树，首先设状态，设 dp_{i,j} 为时间 i，自由的闹钟在 j 位置时的最小花费。

转移有两种。

第一种是由上一个时间点的自由闹钟完成这一时间点的任务，则这一个时间点的自由闹钟一定是前一个的任务闹钟，有转移：

dp_{i,k_{i-1}}=\max (dp_{i-1,j}+\left|j-k_i\right|)

第二种是由上一个时间点的任务闹钟完成这一时间点的任务，则这一个时间点的自由闹钟一定还是前一个的自由闹钟，有转移：

dp_{i,j}=dp_{i-1,j}+\left| k_i-k_{i-1} \right|

发现 dp_{i,j} 转移只与 dp_{i-1} 有关，所以可以滚掉一维。

考虑把第一个式子的绝对值拆开。

dp_{i,k_{i-1}}=\max (dp_{i-1,j}-j+k_i),j\leq k_i dp_{i,k_{i-1}}=\max (dp_{i-1,j}+j-k_i),k_i<j

这个时候我们就可以分别维护 dp_{i,j}-j 和 dp_{i,j}+j，发现转移实际上就是支持区间查询最小值、单点修改和全局加，这个东西可以使用线段树轻松实现。

发现位置的值域很大，因此离散化预处理即可。

时间复杂度 O(n\log n)。

#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;
}