RT

形如

$f(i,j)=\max\{f(i,j-1),f(i-1,j)\}+v(i,j)$

的转移是否可以利用线段树进行优化？

$v(i,j)$ 符号不限，但设 $v(i,j)$ 不为 $0$ 的个数是 $k$，$i$ 和 $j$ 的上限是 $n$ 和 $m$，那么保证 $\mathcal O(n+k\log m)$ 的算法可过。