USACO 2020 January Contest, Platinum

Cave Paintings

从下往上,把这行的每个格子向左右/下一行同一列的格子连边,如果连出环了就把环上的点当作一个等价类缩起来。最后会剩下若干棵树,可以用 DP 计算每棵树的答案。

具体实现时可以直接并查集,合并两个连通快时方案数相乘。

https://ideone.com/209nvl

Non-Decreasing Subsequences

矩阵可以求逆。

https://ideone.com/22ImH1

Falling Portals

把世界看成 \(y=-ix+A_i\) 的直线。

不失一般性,考虑 \(A_i>A_{Q_i}\) 的情形,最优的策略一定是​每次走到若干条直线的交点时,选取斜率最小(下降得最快)的那条直线走。那么,\(i\) 能走到 \(Q_i\) 当且仅当 \(Q_i\) 的直线与所有 \(A_j \ge A_i\) 的直线形成的下凸壳有交,且交点的横坐标就是最优解。

https://ideone.com/dcygWL

上一篇:USACO 2020 January Contest, Platinum Problem 1. Cave Paintings


下一篇:Dijkstra+二分查找