题解：P7823 「RdOI R3」闹钟

int4399 · 2025-12-03 22:02:20 · 题解

题意：

有一个长为 n 的序列 k 和两个初始为 0 的变量 a,b，你需要保证 \forall1\le i\le n,a=k_i \operatorname{or} b=k_i，你可以将变量 a/b 变为 y，代价是 |a/b-y|。求完成任务的最小代价。

我们发现只在每个元素之前至多进行一次操作一定不劣，因为我们只会将一个变量赋值成 k_i，那另一个在之后再改值一定不劣。

先考虑最暴力的 dp。设 f_{i,j,k} 表示处理到第 i 个元素，一个值为 j，一个值为 k 的最小代价。但我们发现转移时一定有一维是 k_i，所以先压了这一维，于是状态变为：f_{i,j} 表示当前处理到第 i 个元素，当前不是 k_i 的变量值是多少。

转移：

• 用上次的变量接着操作：f_{i,j}=f_{i-1,j}+|k_i-k_{i-1}|。
• 换一个变量操作，那么当前不是 k_i 的变量一定是 k_{i-1}，也就是：f_{i,k_{i-1}}=\min\limits_{j=0}^V f_{i-1,j}+|k_i-j|，去绝对值，变成：f_{i,k_{i-1}}=\min(k_i+\min\limits_{j=0}^{k_i} f_{i-1,j}-j,-k_i+\min\limits_{j=k_i}^{V} f_{i-1,j}+j)。

离散化一下，然后用线段树维护即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define P pair<long long,long long>
using namespace std;
const ll N=1e5+5;
ll n,k[N],b[N],minn[N<<2],mi[N<<2],tag[N<<2],tot;
void pushdown(ll u){
    tag[u<<1]+=tag[u],tag[u<<1|1]+=tag[u];
    mi[u<<1]+=tag[u],mi[u<<1|1]+=tag[u];
    minn[u<<1]+=tag[u],minn[u<<1|1]+=tag[u],tag[u]=0;
}
void pushup(ll u){minn[u]=min(minn[u<<1],minn[u<<1|1]),mi[u]=min(mi[u<<1],mi[u<<1|1]);}
void add(ll x){tag[1]+=x,mi[1]+=x,minn[1]+=x;}
void modify(ll u,ll l,ll r,ll pos,ll v){
    if(l==r){mi[u]=min(mi[u],v-b[l]),minn[u]=min(minn[u],v+b[l]);return;}
    pushdown(u);
    if(pos<=mid) modify(u<<1,l,mid,pos,v);
    else modify(u<<1|1,mid+1,r,pos,v);
    pushup(u);
}
P query(ll u,ll l,ll r,ll L,ll R){
    if(L<=l&&r<=R) return {minn[u],mi[u]};pushdown(u);
    if(L<=mid&&mid<R){
        P a=query(u<<1,l,mid,L,R),b=query(u<<1|1,mid+1,r,L,R);
        return {min(a.first,b.first),min(a.second,b.second)};
    }else if(L<=mid) return query(u<<1,l,mid,L,R);
    return query(u<<1|1,mid+1,r,L,R);
}
ll solve(ll u,ll l,ll r){
    if(l==r) return mi[u]+b[l];
    return pushdown(u),min(solve(u<<1,l,mid),solve(u<<1|1,mid+1,r));
}
int main(){
    cin>>n;memset(minn,0x3f,sizeof(minn)),memset(mi,0x3f,sizeof(mi));
    for(ll i=1;i<=n;i++) cin>>k[i],b[i]=k[i];
    sort(b+1,b+1+n),tot=unique(b+1,b+1+n)-b-1;
    for(ll i=1;i<=n;i++) k[i]=lower_bound(b+1,b+1+tot,k[i])-b;
    modify(1,0,tot,0,0);
    for(ll i=1;i<=n;i++){
        ll q1=query(1,0,tot,0,k[i]).second,q2=query(1,0,tot,k[i],tot).first;
        add(abs(b[k[i]]-b[k[i-1]]));
        modify(1,0,tot,k[i-1],min(q1+b[k[i]],q2-b[k[i]]));    
    }
    return cout<<solve(1,0,tot)<<'\n',0;
}