Cave Paintings
从下往上,把这行的每个格子向左右/下一行同一列的格子连边,如果连出环了就把环上的点当作一个等价类缩起来。最后会剩下若干棵树,可以用 DP 计算每棵树的答案。
具体实现时可以直接并查集,合并两个连通快时方案数相乘。
Non-Decreasing Subsequences
矩阵可以求逆。
Falling Portals
把世界看成 \(y=-ix+A_i\) 的直线。
不失一般性,考虑 \(A_i>A_{Q_i}\) 的情形,最优的策略一定是每次走到若干条直线的交点时,选取斜率最小(下降得最快)的那条直线走。那么,\(i\) 能走到 \(Q_i\) 当且仅当 \(Q_i\) 的直线与所有 \(A_j \ge A_i\) 的直线形成的下凸壳有交,且交点的横坐标就是最优解。