题解【CF1316E Team Building】

题目传送门

状压 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}\)。

代码。