题目描述

小塔经常从小红书上的笔记中获得灵感。其中一篇笔记认为，如果有$n$个物品，可以把所有物品分为两类，这些物品摆成一排，如果相邻的两个物品属于不同的类别，那么不美观程度就会加一。

思路：动态规划

定义$dp[i][num][j]$为考虑前$i$个元素且当前存在$j$个$1$（可移动）且以元素$num$结尾的最小答案.

如果当前物品不能移动，那么有 $dp[i][num][j]=min(dp[i][num][j],dp[i-1][0/1][num-currentOne]+(currentOne\space xor\space k))$。

如果当前物品可以移动，那么还需要更新dp数组中可以移动的部分，转移方程同上。

每次更新仅用到了$i-1$的状态，因此可以使用滚动数组优化掉第一维空间。