发现尽管 \(n\) 比较大,但 \(m\) 非常小,于是考虑状压。
记 \(dp_{i}\) 表示满足条件的乐队集合为 \(i\) 时的最小出队人数,\(dp_i=\min\{dp_{i\ \ xor\ \ 1<<k}\}+w_{i\ \ xor\ \ 1<<k,k}\),其中 \(w_{i,j}\) 表示当前状态为 \(i\) 时 \(j\) 对应的区间内未归位的人数。
用 \(sum_i\) 表示队伍 \(i\) 的人数。
预处理 \(w_{i,j}\),先记录前缀和数组 \(s_{i,j}\) 代表前 \(i\) 人里,属于 \(j\) 乐队的人数,那么 \(w_{i,j}=sum_i-s_{i,j}\)。
标签:洛谷,大合唱,题解,sum,P3694,dp From: https://www.cnblogs.com/wapmhac/p/16599279.html