关于动态DP
  • 板块学术版
  • 楼主WrongAnwser
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/9/13 20:56
  • 上次更新2023/11/5 13:13:44
查看原帖
关于动态DP
109801
WrongAnwser楼主2020/9/13 20:56

比如说模板题:

[fs,0fs,1]×[gx,0gx,0gx,1]=[fx,0fx,1]\begin{bmatrix} f_{s, 0}\\ f_{s, 1} \end{bmatrix} \times \begin{bmatrix} g_{x,0} & g_{x, 0}\\ g_{x,1} & -\infty \end{bmatrix} = \begin{bmatrix} f_{x, 0}\\ f_{x, 1} \end{bmatrix}

如果维护gg那个矩阵的连乘,那么那个-\infty就不会再是-\infty了,第一遍会成为gx,0+gx,1g_{x, 0} + g_{x, 1}(显然比俩-\infty加起来大)

比如这篇题解如果我没理解错的话 作者是把一条重链上的gg矩阵连乘起来,在他的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}}}
2020/9/13 20:56
加载中...