动态 DP

INFO

参考：DP 优化方法大杂烩 I.

广义矩阵乘法

对于运算 $(\otimes ,\oplus )$ 来说，矩阵乘法定义为

$$c_{ij}=\underset{k=1}{\overset{n}{⨁}}{a}_{ik}\otimes b_{kj}$$

要求：

• $\oplus$ 有交换律，即 $a\oplus b=b\oplus a$；
• $\otimes$ 具有结合律和交换律，即 $(a\otimes b)\otimes c=a\otimes (b\otimes c)$ 和 $a\otimes b=b\otimes a$；
• $\otimes$ 对 $\oplus$ 有分配律，即 $a\otimes (b\oplus c)=(a\otimes b)\oplus (a\otimes c)$。

例如 $(\pm ,\max )$ 和 $(\wedge ,\vee )$。