题解--闹钟
abruce
·
·
个人记录
小清新 dp 题，思路来源于一次 cf 看错题。
40~70pts
考虑到我们在第 i 天的 a_1,a_2 一定有一个和 k_{i-1} 一样。所以只要记录一下另一个的值就可以 dp 转移。f_{i,j}=f_{i-1,j}+|k_i-k_{i-1}|,f_{i,k_{i-1}}=\min\limits_{j=1}^{100}(f_{i,k_{i-1}},f_{i-1,j}+|j-k_i|)。
能不能拿到 70 分取决于有没有写离散化。
100pts
我们发现对于 a 的选择一定是像下图这样：
因此我们可以只在 a 的选择变化的时候进行转移，中间不变化的部分可以直接算出来。
因为我们只在 a 的选择变化的时候进行转移，所以我们可以知道另外一个里面填的是什么，如下图：
所以转移方程就出来了：
但这个转移方程还是 $O(n^2)$ 的，我们考虑怎么优化。
首先绝对值就很不优美，我们把它拆成两部分分开讨论，以 $k_{j-1}>k_i$ 为例。
剩下的东西我们在 $j$ 这个地方把 $f_j-sum_j+k_{j-1}$ 丢进线段树里，然后在 $i$ 这个地方查询 $[k_i+1,\infty)$ 中线段树里的最小值，然后加上 $sum_{i-1}-k_i$ 即可。
反过来也是一样的。
这样就做完了，上代码，注意特判一直选 $a_1$ 的情况。
```cpp
#include <bits/stdc++.h>
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
struct Seg {
struct tree {
int c[2];
ll sum;
} t[maxn*30];
int cnt;
void add(int &id,int l,int r,int v,ll k) {
if(!id)id=++cnt,t[id].sum=1e18;
t[id].sum=min(t[id].sum,k);
if(l==r)return;
int mid=l+r>>1;
v<=mid?add(lc(id),l,mid,v,k):add(rc(id),mid+1,r,v,k);
}
ll ask(int id,int l,int r,int L,int R) {
if(!id)return 1e18;
if(l>=L&&r<=R)return t[id].sum;
int mid=l+r>>1;
ll sum=1e18;
if(L<=mid)sum=min(sum,ask(lc(id),l,mid,L,R));
if(R>mid)sum=min(sum,ask(rc(id),mid+1,r,L,R));
return sum;
}
} t[2];
ll f[maxn],tag,sum[maxn],ans=1e18;
int n,a[maxn],rt[2];
int main() {
scanf("%d",&n);
for(register int i=1; i<=n; i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+abs(a[i]-a[i-1]);
ans=sum[n];
f[1]=a[1];
t[0].add(rt[0],0,1e9,0,a[1]-sum[1]);
for(register int i=2; i<=n; i++) {
f[i]=min(t[0].ask(rt[0],0,1e9,0,a[i]-1)+a[i],t[1].ask(rt[1],0,1e9,a[i],1e9)-a[i])+sum[i-1];
ans=min(ans,f[i]+sum[n]-sum[i]);
t[0].add(rt[0],0,1e9,a[i-1],f[i]-sum[i]-a[i-1]);
t[1].add(rt[1],0,1e9,a[i-1],f[i]-sum[i]+a[i-1]);
}
printf("%lld",ans);
return 0;
}
```