I题:要求矩阵的最大子矩阵和,其中第i行第j列是ai*bj。

经过代数变形问题等价求:a的连续子段和b的连续子段和.
考虑到有负数存在,我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。
答案就是最值
最值(4种可能)

j题:给出一个有根树,1为根。给出节点颜色,要求红节点的子树点权和是3的倍数。

每个点的点权为1或2,给出任意一种构造方案。
解法:分析可知两种情况下无法构造

  • 红叶子没有子节点,子树和无法到3.
  • 红节点的儿子不存在白节点