会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要把 n 件标本排成一排，同时满足「同 type 位置差 ≥ minGap」「相邻 diet 不同」「珍稀标本只能放位置 0 或 n−1」三条规则，并使总观赏值最大。
第一步：把常数项摘出来。 总观赏值 = 各标本 score 之和 + 相邻标本对的 bonus 之和。前一项与排列无关，是定值，所以只需要最大化相邻加成之和，最后再加回去。
第二步：确定用什么刻画「已经排好的前缀」。 n≤15，位置从左往右依次填写，最自然的做法是状压 DP：用位掩码 mask 记录「已经放了哪些标本」，还没填的位置下标就是 pos = popcount(mask)。
三条规则对「历史信息」的需求并不一样：
