补题的时候想了半天交换后对01和10个数的影响，写了半天的dp才发现前面的修改会影响0和1的个数(我是shabi)
不过我感觉应该还是可做的
直接说正解。首先显然我们不需要同时记录0的个数和1的个数，因为知道一个可以通过\(i-cnt\)得到另一个
仔细一想，我们其实也不需要同时记录\(cnt01\)和\(cnt10\)的个数。因为原题的操作是交换，所以总的0和1的个数是不会改变的，而且容易得到如果\(cnt01 = cnt10\)，则\(cnt01 = cnt10 = \frac{cnt0 \times cnt1}{2}\)
所以我们可以设\(dp_{i,cnt0,cnt01}\)表示前\(i\)个数有\(cnt0\)个0，\(cnt01\)个01的最少交换次数
容易得到递推柿：
\[\begin{align} dp_{i,cnt0,cnt01} &\leftarrow dp_{i-1,cnt0 - 1,cnt01} \ (a_i=0)\\ dp_{i,cnt0,cnt01} &\leftarrow dp_{i-1,cnt0, cnt01 - cnt0} + 1 \ (a_i=0)\\ dp_{i,cnt0,cnt01} &\leftarrow dp_{i-1,cnt0,cnt01-cnt0} \ (a_i=1)\\ dp_{i,cnt0,cnt01} &\leftarrow dp_{i-1,cnt0 - 1, cnt01} + 1 \ (a_i=1)\\ \end{align} \]最终答案即为\(dp_{n,cnt0,\frac{cnt0 \times cnt1}{2}}\)
总复杂度\(O(n^4)\)
标签：cnt10,leftarrow,个数,cnt01,CF1860D,cnt0,dp From： https://www.cnblogs.com/fox-konata/p/17642016.html