首页 > 代码库 > [luoguP3694] 邦邦的大合唱站队／签到题（状压DP）
[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[length-num[j]][j]));f[i]=min(f[i xor 2?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 x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; return x * f;}int main(){ int i, j, x; n = read(); m = read(); memset(f, 127, sizeof(f)); for(i = 1; i <= n; i++) { x = read(); num[x]++; for(j = 1; j <= m; j++) sum[i][j] = sum[i - 1][j] + (x == j); } f[0] = 0; for(i = 1; i < (1 << m); i++) { S = 0; for(j = 1; j <= m; j++) if(i & (1 << j - 1)) S += num[j]; for(j = 1; j <= m; j++) if(i & (1 << j - 1)) { cnt = num[j] - sum[S][j] + sum[S - num[j]][j]; f[i] = min(f[i], f[i ^ (1 << j - 1)] + cnt); } } printf("%d\n", f[(1 << m) - 1]); return 0;}
[luoguP3694] 邦邦的大合唱站队／签到题（状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。