分享CF一个状压题
<–点个👍呗
题目描述
Vladislav有一个由$n$首歌曲组成的播放列表,编号从$1$到$n$。第$i$首歌曲的流派为$g_i$,作者为$w_i$。他想要制作一个播放列表,使得每对相邻的歌曲要么具有相同的作者,要么来自相同的流派(或两者兼而有之)。他称这样的播放列表为令人兴奋的。其中$g_i$和$w_i$都是长度不超过$10^4$的字符串。
可能并不总是能够使用所有歌曲制作一个令人兴奋的播放列表,因此洗牌过程分为两步。首先,一些歌曲(可能为零)被移除,然后播放列表中剩余的歌曲被重新排列以使其变得令人兴奋。
由于Vladislav不喜欢从他的播放列表中移除歌曲,他希望制作播放列表时尽量减少移除的数量。帮助他找到需要执行的最小移除次数,以便能够重新排列其余的歌曲,使播放列表变得令人兴奋。
输入
输入的第一行包含一个整数$t$ ($1 \le t \le 1000$) — 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数$n$ ($1 \le n \le 16$) — 原始播放列表中歌曲的数量。
接下来是$n$行,每行包含两个小写字母字符串$g_i$和$w_i$ ($1 \leq |g_i|, |w_i| \leq 10^4$) — 第$i$首歌曲的流派和作者。其中$|g_i|$和$|w_i|$分别表示字符串的长度。
所有测试用例中$2^n$的总和不超过$2^{16}$。
所有测试用例中$|g_i| + |w_i|$的总和不超过$4 \cdot 10^5$。
输出
对于每个测试用例,输出一个整数 — 所需的最小移除次数,以便使得生成的播放列表变得令人兴奋。
样例
4
1
pop taylorswift
4
electronic themotans
electronic carlasdreams
pop themotans
pop irinarimes
7
rap eminem
rap drdre
rap kanyewest
pop taylorswift
indierock arcticmonkeys
indierock arcticmonkeys
punkrock theoffspring
4
a b
c d
e f
g h
说明
在第一个测试用例中,播放列表已经是令人兴奋的。
在第二个测试用例中,如果你按照$4, 3, 1, 2$的顺序排列歌曲,它就是令人兴奋的,因此你不需要移除任何歌曲。
在第三个测试用例中,你可以移除歌曲$4, 5, 6, 7$。然后,按照$1, 2, 3$的顺序排列歌曲,播放列表就变得令人兴奋了。
解题思路
个人感觉这题与前几天蓝桥杯每日一题中的毕业旅行问题很相似,该题解题思路具体如下:
(1)定义f[i][j]表示的集合为“状态i表示的歌曲所有的合法排列(且每个排列最后一首歌必须为j)组成的集合”
(2)属性为max
(3)同“毕业旅行问题”一样,这里需要枚举倒数第二首歌是什么,如果倒数第二首歌流派或者作者有一个同j一样,则可以转换过来,即g[(倒数第二首歌,j)] = True
(4)有3可以得出状态转移方程为f[i][j] = max(f[i][j], 1 + f[t][k]),这里t表示状态i去除j后的状态,k表示倒数第二首歌
Python代码如下
import sys
input = lambda: sys.stdin.readline().rstrip()
def solve():
n = int(input())
info = [input().split() for i in range(n)]
#预处理第i首歌和第j首个是不是有相同流派或作者(从0开始编号)
g = dict()
for i in range(n):
for j in range(n):
if info[i][0] == info[j][0] or info[i][1] == info[j][1]:
g[(i, j)] = g[(j, i)] = True
else:
g[(i, j)] = g[(j, i)] = False
#预处理每个状态中1的位置,用key-value存储更方便
p = dict()
for i in range(1 << n):
t = []
for j in range(n):
if (i >> j) & 1:
t.append(j)
p[i] = t
#因为是求最大值,因此初始时f全为0(非法状态f[i][j]从始至终都是0)
#合法状态最小为1(见下方代码)
f = [[0 for i in range(n)] for i in range(1 << n)]
for i in range(1, 1 << n):
for j in p[i]:
#p[i]存储了状态i的所有1所在位置,因此f[i][j]合法,哪怕i中只选j其余都不选,也至少有1首歌
f[i][j] = 1
t = i - (1 << j)#状态i中去除j,
for k in p[t]:#枚举倒数第二首歌,k表示倒数第二首歌
if g[(j, k)]:#这两首歌流派或作者相同
f[i][j] = max(f[i][j], 1 + f[t][k])
#题目要求最少删除多少歌,即最多能保留多少歌
print(n - max(f[(1 << n) - 1]))
for _ in range(int(input())):
solve()