@[Fading](/space/show?uid=20309) 听某大佬说,其实可以不用改写什么矩阵乘法,可以直接用线段树维护DP状态
by ddwqwq @ 2019-01-12 12:24:00
@[杜岱玮](/space/show?uid=64366) Orz
by Fading @ 2019-01-12 12:25:53
@[杜岱玮](/space/show?uid=64366) 其实原理差不多吧……矩阵乘法模拟的也是 dp 转移。
就像你用 a[1][1], a[1][2], a[2][1], a[2][2] 做 2\*2 矩阵乘法和用 a, b, c, d 做矩阵乘法是等价的一样。
by tiger0133 @ 2019-01-12 12:29:52
@[杜岱玮](/space/show?uid=64366) 用矩阵乘法的原因就是因为这种dp有结合律啊...
by bzy369258147 @ 2019-01-12 12:36:32
@[Fading](/space/show?uid=20309) 有吧
$\begin{bmatrix}0&-\infty\\-\infty&0\end{bmatrix}$
by ljc1301 @ 2019-01-12 13:02:22
@[ljc1301](/space/show?uid=36998) 好像很有道理
by Fading @ 2019-01-12 13:11:57
@[ljc1301](/space/show?uid=36998) %%%
by Fading @ 2019-01-12 13:12:07