1950G - 随机播放歌曲 官方标程题解 + 完整 AC 代码

（格式严格规范：公式、数字、变量全加 $\$$，$n\le 16$ 状压DP 标准解法）

一、题意回顾（最简版）

给定 $n$ 首歌（$n\le 16$），每首歌有流派 $g_i$、作者 $w_i$。

要求选出最多的歌，可以排成一个序列，满足： 相邻两首歌 流派相同 或 作者相同。

答案 = $n -$ 最多保留歌数。

二、标程核心思路

1. 字符串归一化（坐标压缩）

把字符串映射为数字，避免频繁比较字符串超时。

2. 状压 DP 定义（官方标准）

• $mask$：二进制集合，表示选了哪些歌
• $i$：序列最后一首歌是 $i$
• 含义：能否以歌 $i$ 结尾，选出 $mask$ 里的歌并排成合法序列

3. 转移方程

如果歌 $j$ 没选，且 歌 $i$ 与歌 $j$ 合法相邻：

4. 答案

所有 $dp[mask][i]=true$ 中，最多二进制 $1$ 的数量。 最少删除数 = $n - \text{max\_cnt}$。

三、标程总结（3 条必背）

1. $n\le 16$ → 状压DP
2. $dp[mask][i]$：选 $mask$，以 $i$ 结尾是否合法
3. 转移：能接就接，最后统计最大合法长度

需要我给你逐行讲解代码或生成对拍器吗？