定义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 xor k))。
如果当前物品可以移动,那么还需要更新dp数组中可以移动的部分,转移方程同上。
有 n 张卡片排成一列,每张卡片颜色为黑色(用 1 表示)或白色(用 2 表示)。现在给出一个固定标记数组,标记为 0 的卡片位置固定不能移动,标记为 1 的卡片可以自由移动。你可以任意重排所有可移动卡片的位置(但不能改变不可移动卡片的位置),问重新排列后,整个序列中相邻卡片颜色不同的位置总数的最小值是多少。
卡片数量 n 满足 1≤n≤100,颜色 ai 的值只可能是 1 或 2,固定标记 bi 只可能是 0 或 1。
第一行包含一个整数 n。 第二行包含 n 个整数 a1,a2,…,an,表示初始时每张卡片的颜色。 第三行包含 n 个整数 b1,b2,…,bn,其中 bi=0 表示第 i 张卡片不可移动,bi=1 表示可移动。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册