定义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的状态,因此可以使用滚动数组优化掉第一维空间。
小红经常从小红书上的笔记中获得灵感。其中一篇笔记认为,如果有n个物品,可以把所有物品分为两类,这些物品摆成一排,如果相邻的两个物品属于不同的类别,那么不美观程度就会加一。
现在小红有n个物品,其中一些物品不方便移动,另一些物品可以移动。小红想知道,如何移动其中可以移动的物品,使得不美观程度最小。
第一行输入一个整数n(1≤n≤100),表示物品的数量。第二行输入n个整数a1,a2,…,an(ai∈[1,2])代表物品类别。其中ai=1表示物品是第一类,ai=2表示物品是第二类。
第三行输入n个整数b1,b2,…,bn(bi∈[0,1])代表物品是否可被移动。其中bi=1表示第i个物品可以移动,bi=0表示第i个物品不可以移动。
在一行上输出一个正整数,表示不美观程度的最小值。
输入
5
1 2 1 2 1
0 1 1 0 1
输出
1
提示
交换第二个和第五个物品,可以使得不美观程度最小。此时物品类别为[1,1,1,2,2]。