1000ms

Difficulty: 7

所属公司 : 小红书

时间 :2024年9月1日

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

思路：动态规划

定义 $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数组中可以移动的部分，转移方程同上。

题目描述

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