传送门
来自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[ixor2j]+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; }
上一篇：[luoguP2015] 二叉苹果树（DP）
下一篇：[luoguP1273] 有线电视网（DP）
DP
