ARC070 简要题解

A

~~往厕所里一蹲~~

然后发现对于 (i) , ([1, frac{i(i+1)}{2}]) 的点均可达

没了

我有一个绝妙的思路

首先一个数 (a_i) 会产生影响当且仅当能够有若干个数的和在 ([k - a_i, k)) 内

前缀跑一遍背包, 后缀跑一遍, bitset 优化一下, 然后把后缀的 reverse 一下

对于每一个点讨论 ([k - a_i, k)) 中的每一个值

发现对应的是前缀背包和后缀背包的一段卷积, 正好后缀又 reverse 了

所以就会是前缀背包的一段前缀 , 和后缀 reverse 过的背包的一段前缀 , 与一下, 看有没有 1

没写过所以不知道复杂度

网上的解法是这样的

可有可无的数必定是从最小值开始的一段连续的数

证明挺简单的

所以二分, 然后 check 里面跑背包, bitset 优化

复杂度 (O(frac{N^2log N}{64}))

暴力 DP 很好想, 设 (f[i][j]) 为第 (i) 个矩形左端点放到 (j) 的最小花费

设 (len_i) 为第 (i) 个区间的长度, (l_i, r_i) 为第 (i) 个区间左, 右端点, 则有

[f[i][j] = min(f[i - 1][k])+|j-l_i|, k in [j-len_i+1,j+len_{i-1}-1] ]

范围可能写错了, 最好是自己手推一下

然后那个 (min) 里面那个式子是一个斜率依次递增的直线构成的凸包, 右边那个是个 "V" 型函数

发现跟 [APIO2016]烟火表演挺像的

不妨设斜率为零的那部分的横坐标是 ([l, r]) , 我们把 DP 方程换一换, 设 (f_i(x)) 为第 (i) 个矩形左端点在 (x) 的最小花费

先设 (L = len_i - 1, R = len_{i+1}-1)

那么就会有

[f_{i+1}(x)=egin{cases}|x-l_{i+1}|+f_i(x+R), xin(-infin, l-R)\|x-l_{i+1}|+f_i(l), xin[l-R,r+L]\|x-l_{i+1}|+f_i(x-L),xin(r+L,+infin)end{cases} ]

原因是如果决策区间中不包含斜率为 (0) 的那一段的横坐标那就尽量靠近斜率为 (0) 的选, 这样花费少

如果包含就选上

发现上面那个东西就是把原来 (f_i) 函数的 ((-infin, l]) 左移 (R) , ([r, +infin)) 右移 (L) , 然后再插进去一个 (|x-l_{i+1}|) 函数

可以用堆维护拐点, 因为左边也要平移, 右边也要平移, 一个拐点代表在这个点斜率加了 (1)

所以写两个堆, 一个存斜率为 (0) 直线左边的拐点, 一个存右边的

然后按上面的转移即可

先咕着