コイン拾い / Coin

· · 题解

由于走过一个格子时最多得到一枚硬币，并且走到该格子必然存在最少与最大获得金币数。那么所得到的金币数一定在一个区间里，可以用差分处理答案。

为得到该区间两端点，定义 f(i,j),g(i,j) 分别表示到达点 (i,j) 所得的最小及最大金币数。转移式如下：

\begin{aligned} f(i,j) & = \min\{f(i-1,j),f(i,j-1)\}+p\\ g(i,j) & = \max\{g(i-1,j),g(i,j-1)\}+p \end{aligned}

其中只有当 (i,j) 处有硬币时 p=1，否则 p=0。

时间复杂度 O(N^2)。

代码与记录