题解【CF1316E Team Building】

UperFicial · 2022-09-05 16:01:12 · 题解

题目传送门

同步发表于我的 cnblogs。

状压 DP 入门题。

设 f_{i,S} 表示考虑了前 i 个人，队伍放置情况为 S 时（0 表示放置了队员，1 表示没有放置）的最大贡献。

然后分讨一下 i 是去当队员，还是当观众，还是摆烂。

如果 i 当队员，那么枚举一下 i 被放在了哪一个位置上，记为 j，这时需要满足 S 二进制下的第 (j-1) 位是 1，然后直接转移就行了，f_{i,S}=f_{i,S\oplus 2^{j-1}}+s_{i,j}。

下面就选择当观众还是摆烂问题。我们贪心一下，将 a 从大到小排序，这样，能当观众就当观众的策略一定是最优的。

所以我们只需要考虑当前观众数量是否小于 k。如果小于 k，那么 i 肯定当观众 f_{i,S}=f_{i-1,S}+a_i，否则摆烂 f_{i,S}=f_{i-1,S}。

代码。