[luoguP3694] 邦邦的大合唱站队／签到题（状压DP）

传送门

来自kkk的题解：

70分做法：枚举每个学校顺序，暴力。

100分：状压dp。从队列头到尾DP，

状态：f[i]表示i状态下最小的出列（不一致）的个数。

比如f[1101]表示从头到位为1/3/4乐队的偶像的最小出列个数。

f[i]=min(f[i\ xor\ 2^j]+num[j](sum[length][j]sum[lengthnum[j]][j]));f[i]=min(f[ixor2?j??]+num[j]?(sum[length][j]?sum[length?num[j]][j]));

j表示团队编号，sum表示某种团队的前缀和，length表示到此已经排到的长度。

#include <cstdio> #include <cstring> #include <iostream> #define M 21 #define N 100001 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, m, S, cnt; int sum[N][M], num[M], f[1 << M]; inline int read() int main() f[0] = 0; for(i = 1; i < (1 << m); i++) } printf("%d\n", f[(1 << m) 1]); return 0; }

　　

上一篇：[luoguP3092] [USACO13NOV]没有找零No Change（状压DP + 二分）

下一篇：[luoguP2831] 愤怒的小鸟（状压DP）

---

DP