设$f_i$表示从1到i节点的最多金币数,$g_i$表示从i到n节点的最多金币数
一个矩阵限制了一定区间不能走,同时也规定了只能通过如下四种方法走过来
蓝色表示障碍矩阵,要么在绿色矩阵中选择一个节点x,经过绿色区域一定会避开蓝色矩阵
要么从上方的红色区间选择一个点,然后从右方的红色区间选择一个点,这样也可以避开蓝色矩阵
同理
选择从下方过来如上,依旧有两种情况
先用树状数组求出$f_i,g_i$,然后再用树状数组求出前缀区间或者后缀区间最大值即可
CODE:
标签:杭电多校,矩阵,2024,4L,区间,节点 From: https://www.cnblogs.com/handsome-zlk/p/18333508