题解：P7823 「RdOI R3」闹钟
xiezheyuan
·
·
题解
简要题意
有两个变量 x,y，初始时有 x=y=0。
每个时刻开始时你可以进行一次调整，一次调整可令一个变量增加或减少任意一个值，花费等量代价。
有 n 个时刻，每个时刻有一个整数 k_i，表示这个时刻结束时需要有至少一个变量等于 k_i。
求花费的最小的代价和。
## 思路
设 $f(i,j)$ 表示在第 $i$ 个时刻，两个变量的值为 $k_i,j$ 的最小代价。
则不难有两种转移：
$$
f(i,j)=\begin{cases}
f(i-1,j)+|k_i-k_{i-1}|& j\neq k_{i-1}\\
\min\limits_{t=0}^{+\infty} f(i-1,t)+|k_i-t|& j=k_{i-1}
\end{cases}
$$
简单解释一下转移的含义。第一种转移是让以前为 $k_{i-1}$ 的变量的值变成 $k_i$，而第二种转移是让以前不为 $k_{i-1}$ 的变量（或者两者均为 $k_{i-1}$ 的情况下其中的一个变量）的值变为 $k_i$。
我们发现第二种情况下，$j$ 的取值一定在 $k$ 中更优秀（我们不会无缘无故将 $j$ 变成一个毫不相干的数），我们将 $k$ 离散化作为 $j$ 这一维下标，这样可以做到 $O(n^2)$。难以通过本题，我们需要优化。
不难发现除了 $j=k_{i-1}$ 的位置外，其余的位置都是增加了一个定值 $|k_i-k_{i-1}|$。
而对于 $j=k_{i-1}$ 的情况，则是每个位置加上一个绝对值之后求全局最小值。
考虑绝对值我们应当怎么处理。可以将满足 $t\leq k_{i-1}$ 的所有位置加上 $k_i$ 减去 $t$。$t>k_{i-1}$ 同理。
加上 $k_{i-1}$ 相对好处理，不过减去 $t$ 就有难度。我们可以维护 $f'(i,j)=f(i,j)-j,f''(i,j)=f(i,j)+j$，这样子求最小值的时候可以拆成两个部分求最小值。
现在，我们需要找一个数据结构来维护 dp，需要支持区间加区间查询最小值，线段树可以胜任。
时间复杂度 $O(n\log n)$。
## 代码
```cpp
#include <bits/stdc++.h>
#define int long long
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 5, inf = 1e18;
int n, a[N], b[N], trs[N], rev[N];
struct sgt{
int t[N << 2], tag[N << 2];
void build(int i, int l, int r){
if(l == r) return t[i] = ((l == 1) ? 0 : inf), void();
build(ls, l, mid);
build(rs, mid+1, r);
t[i] = min(t[ls], t[rs]);
}
void mktag(int i, int v){ t[i] += v, tag[i] += v; }
void pushdown(int i){ mktag(ls, tag[i]), mktag(rs, tag[i]), tag[i] = 0; }
void update(int ql, int qr, int v, int i, int l, int r){
if(ql <= l && r <= qr) return mktag(i, v);
pushdown(i);
if(ql <= mid) update(ql, qr, v, ls, l, mid);
if(mid < qr) update(ql, qr, v, rs, mid+1, r);
t[i] = min(t[ls], t[rs]);
}
int query(int ql, int qr, int i, int l, int r){
if(ql > qr) return inf;
if(ql <= l && r <= qr) return t[i];
pushdown(i);
int res = inf;
if(ql <= mid) res = min(res, query(ql, qr, ls, l, mid));
if(mid < qr) res = min(res, query(ql, qr, rs, mid+1, r));
return res;
}
void assign(int p, int v, int i, int l, int r){
if(l == r) return t[i] = v, void();
pushdown(i);
if(p <= mid) assign(p, v, ls, l, mid);
else assign(p, v, rs, mid+1, r);
t[i] = min(t[ls], t[rs]);
}
} t, tp, tn;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i], b[i] = a[i];
int tot = n; b[++tot] = 0;
sort(b+1, b+tot+1);
tot = unique(b+1, b+n+1) - b;
for(int i=1;i<=n;i++){
trs[i] = lower_bound(b+1, b+tot+1, a[i]) - b;
rev[trs[i]] = i;
}
// cerr << tot << '\n';
// for(int i=1;i<=tot;i++) cerr << a[rev[i]] << ' ';
// cerr << '\n';
trs[0] = 1, rev[1] = 0;
t.build(1, 1, tot);
tp.build(1, 1, tot);
tn.build(1, 1, tot);
for(int i=1;i<=n;i++){
int rt = min(tn.query(1, trs[i], 1, 1, tot) + a[i], tp.query(trs[i] + 1, tot, 1, 1, tot) - a[i]);
t.update(1, tot, abs(a[i] - a[i - 1]), 1, 1, tot);
tp.update(1, tot, abs(a[i] - a[i - 1]), 1, 1, tot);
tn.update(1, tot, abs(a[i] - a[i - 1]), 1, 1, tot);
t.assign(trs[i - 1], rt, 1, 1, tot);
tp.assign(trs[i - 1], a[i - 1] + rt, 1, 1, tot);
tn.assign(trs[i - 1], -a[i - 1] + rt, 1, 1, tot);
// for(int j=1;j<=tot;j++) cerr << t.query(j, j, 1, 1, tot) << ' ';
// cerr << '\n';
}
cout << t.query(1, tot, 1, 1, tot) << '\n';
return 0;
}
// Written by xiezheyuan
```