[DP] UOJ84 [UR #7] 水题走四方

好题。容易想错...

为了方便思考,可以设一个人是本体,不会瞬移,另一个是分身,会瞬移。

本体最后一定能停在一个叶子上,把根到这个叶子的链叫做主链。

考虑最优答案一定是:

在主链上选一些关键点,本体在这些位置停留,分身下去把到下个停留点之前的那些叶子遍历。

剩最后一个叶子时,本体同时往下到下个关键点。剩下最后的叶子显然选深度大的优。

现在只需考虑如何选主链,以及上面的关键点。

可以设 \(f(i)\) 表示现在两个人都在 \(i\) 这个关键点,\(i\) 到根已经处理完了,的最小时间。显然暴力 \(DP\) 可以 \(O(n^2)\)

再来考虑有什么结论。注意到转移中应该有个 \(max\) ,就是剩最后一个叶子的情况。

\(dm(i)\) 表示 \(i\) 的分支的叶子的最大深度。

\(v\) 是上个关键点,若 \(dm(v) < d(i)\) ,分身已经到叶子了,本体还没到下个关键点,则分身可以立刻与本体会合。

可以把这个会和点作为关键点,然后增加一个 \(f(i)=f(fa(i))+1\ (fa(i)无分支)\) 的转移。

现在关键点之间转移要满足 \(dm(v) > d(i)\)

还有一个结论,选上个关键点应该只需考虑最近的满足 \(dm(v) > d(i)\) 的点 \(v\) 。比较显然。

然后就好做了,只需求出 \(top(i)\) 表示离 \(i\) 最近的满足 \(dm(v) > d(i)\) 的点 \(v\) 。就可以 \(O(1)\) 转移了。

\(top(i)\) 可以随编求,比较优的方法是 \(dfs\) 加链表,向上不断合并,是 \(O(n)\) 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=5000005,maxe=5000005;
int n,m,pre[maxn];
int d[maxn],sz[maxn],dm[maxn],top[maxn];
LL f[maxn],ds[maxn];
char s[maxn*2];
bool cson[maxn];
LL min(LL x,LL y){ return x<y?x:y; }
LL max(LL x,LL y){ return x>y?x:y; }
void Init(){
scanf("%d%s",&n,s);
int v=0, tot=0;
for(int i=0;i<n*2;i++){
if(s[i]=='(') tot++, pre[tot]=v, v=tot;
else v=pre[v];
}
}
int fir[maxn],nxt[maxe],son[maxe],tot;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int ltop[maxn],lend[maxn],to[maxn];
LL ans=1e18;
int main(){
Init();
d[1]=1;
for(int i=2;i<=n;i++) add(pre[i],i), d[i]=d[pre[i]]+1, cson[pre[i]]=true;
for(int x=n;x>=1;x--){
if(!cson[x]){
sz[x]=1; dm[x]=d[x]; ds[x]=d[x];
}
ltop[x]=lend[x]=x; to[x]=0;
int k=0;
for(int j=fir[x];j;j=nxt[j]){
d[son[j]]=d[x]+1;
sz[x]+=sz[son[j]]; ds[x]+=ds[son[j]]; dm[x]=max(dm[x],dm[son[j]]);
if(dm[k]<dm[son[j]]) k=son[j];
}
int tmp=0;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=k){
tmp=max(tmp,dm[son[j]]);
for(int i=ltop[son[j]];i;i=to[i]) top[i]=x;
}
int p=0; for(int i=ltop[k];i;i=to[i]) if(d[i]<=tmp) p=i, top[i]=x; else break;
if(!p) p=ltop[k]; else p=to[p];
to[lend[x]]=p; lend[x]=lend[k];
}
f[1]=0;
for(int i=2;i<=n;i++){
f[i]=1e18;
if(top[i]) f[i]=f[top[i]]+ds[top[i]]-ds[i]-(LL)(sz[top[i]]-sz[i])*d[top[i]];
if(!nxt[fir[pre[i]]]) f[i]=min(f[i],f[pre[i]]+1);
}
for(int i=1;i<=n;i++) if(!cson[i]) ans=min(ans,f[i]);
printf("%lld\n",ans);
return 0;
}