题解：AT_agc069_a [AGC069A] Schedule Optimization

· · 题解

有迹可循的好题。

考虑把操作树建出来，假设我不能操作怎么判断合法性。

对于一个非叶子节点，设左右儿子比赛出来的合法区间是 [l_1,r_1] 和 [l_2,r_2]，那么两区间不交就无解，否则比赛后的合法区间为 [\max(l_1,l_2),\max(r_1,r_2)]。

一个很好的想法叫做只操作左端点，也就是当合并时发现 l_1\leq r_1<l_2\leq r_2 时，把 l_2\gets r_1，因为左端点越小越好。但是这样是不对的，你不能一边合并一边做操作。

由于 左端点越小越好 和 合并时取 \max 的矛盾，我们先不考虑左端点的操作，考虑只能对右端点做操作会发生什么。

一个点合并后的右端点就是子树内右端点最大值。证明很简单，你右移 r_1 不会让 \max(r_1,r_2) 变大。

所以我们考虑在叶子把左端点做好，在合并过程只考虑右端点即可。考虑 dp，设 f_{x,i} 表示合并之后 l\leq i 的最小代价。转移有

f_{x,i}=\min(f_{x,i-1},f_{\text{lson},i}+f_{\text{rson},i}+\min(i-\min(r_1,r_2),0)).

对于叶子节点 x 有

f_{x,i}=\min(l-i,0).

容易发现 f_{x,*} 是凸的，维护凸包折点即可。时间复杂度 O(2^n\times n)。