首先朴素的想法是，枚举列子集，考虑 DP 行。
你发现每一列上升或者下降的状态都是不确定的，但是很好的一点是，只需要枚举开头两行我们就可以知道所有状态了，此时可以做到 \(O(2^n n^4)\) 或者 \(O(2^n n^3)\)。
但是这是没有优化前景的，考虑这个做法枚举开头从而浪费了后面本质一样的转移过程，所以我们将这相邻两行压入 DP 状态里 DP，可以随便用桶存一下做到 \(O(2^n n^2)\)。
我认为两种做法没有本质差别，或许以后要多想想将限制压入状态里边。
首先朴素的想法是，枚举列子集，考虑 DP 行。
你发现每一列上升或者下降的状态都是不确定的，但是很好的一点是，只需要枚举开头两行我们就可以知道所有状态了，此时可以做到 \(O(2^n n^4)\) 或者 \(O(2^n n^3)\)。
但是这是没有优化前景的，考虑这个做法枚举开头从而浪费了后面本质一样的转移过程，所以我们将这相邻两行压入 DP 状态里 DP，可以随便用桶存一下做到 \(O(2^n n^2)\)。
我认为两种做法没有本质差别，或许以后要多想想将限制压入状态里边。