JSOI2009 题解

Count

二维树状数组板子题，开 \(c\) 个二维树状数组即可过。可以通过离线对每个权值单独操作做到只开一个二维树状数组。如果空间要求更紧的话可以 cdq 分治做到只开一个一般的树状数组，因为这个问题本质上是三维数点。

火星藏宝图

容易想到一个暴力 dp ：\(f_i\) 表示走到第 \(i\) 座岛的最大收益。暴力转移就可以做到 \(\mathcal{O}(n^2)\) 。但观察到一个性质：对于同一列的所有岛屿，肯定从最下面的岛屿转移过来。所以单次转移优化到 \(\mathcal{O}(m)\) ，总复杂度 \(\mathcal{O}(nm)\) ，已经可以通过。把状态改成 \(f_{i,j}\) 表示走到 \((i,j)\) 的最大收益，转移式子明显可以斜率优化，时间复杂度 \(\mathcal{O}(m^2)\) 。