比如说模板题:
[fs,0fs,1]×[gx,0gx,1gx,0−∞]=[fx,0fx,1]
如果维护g那个矩阵的连乘,那么那个−∞就不会再是−∞了,第一遍会成为gx,0+gx,1(显然比俩−∞加起来大)
比如这篇题解, 如果我没理解错的话 作者是把一条重链上的g矩阵连乘起来,在他的34行gtw那个函数加一个断点发现那个重链的mp[2][2]
的确是一个92这样的数,为什么这样对答案没有影响呢?
(断点:)
Breakpoint 1, bst::gtw (this=0x8358640 <bst>, x=@0xbfffeff8: 1, v=@0xbfffeffc: 7) at 1.cpp:34
34 {w[x][1][0]+=mul[v].gmx();w[x][0][0]=w[x][1][0];w[x][0][1]+=max(mul[v][0][0],mul[v][1][0]);fa[v]=x;}
(gdb) p mul[v]
$1 = {mp = {{47, 92}, {0, 92}}}