轮廓线DP，最主要的就是把轮廓给描述出来
这道题目很容易发现一个性质，就是他的轮廓一定是长成阶梯（锯齿）状的
于是我本人想到的一个状态描述就是去描述拐点：用两个二进制数表示行和列的拐点（为\(1\)则表示对应行/列有拐点），最开始从左下开始向上走，遇到行的拐点就变成向右走，遇到列的拐点又变成向上走，如此反复
但是这种状态表示需要判断是否合法，而且转移很麻烦
于是看看这篇题解
这篇题解的想法也比较容易想到，但说实话还是有点麻烦
我们来看看最简单的一种状态
画图之后可以发现每行的棋子数是一个递增序列，即上一行的棋子数一定比下一行多，而且每一行的棋子都是从左往右那么多个，也就是说确定了每一行的棋子数就确定了整个局面，所以关键就是如何简洁地表示一个递增序列
我们可以先写\(m\)个\(0\)，然后看每一行，有几个棋子就在第几个\(0\)后面插入一个\(1\)
首先我们先写出\(5\)个\(0\)，即\(00000\)
然后看第一行，有四个黑点，于是再第四个\(0\)后面放上一个\(1\)，变成\(000010\)
其他行依次类推，最后变成了\(1011010010\)
于是我们可以发现我们放一个棋子，就是把当前状态的某一个子串\(10\)（注意一定是\(1\)在\(0\)的前面，而且两者是挨着的）变成\(01\)（即交换两者顺序），而且只要我们最开始的状态合法，是按这个规则交换的，那么交换后的状态也一定合法
所以代码复杂度要小很多，具体见洛谷
所以以后这种锯齿状的可以考虑这么去描述轮廓
标签：状态,拐点,一行,木棋,棋子,chess,一双,变成,描述 From： https://www.cnblogs.com/dingxingdi/p/18006186