课程安排（状压dp）

题意：让你安排课程，保证每学期的课不能冲突，问最少需要几个学期。

solution：

因为 n 只有15，可以考虑状压dp。用二进制每位的1/0表示当前是否学习该课程，可以得到 n 个二进制位，那么所有的可能性有 1<<n 种，预处理 g[s] 表示 s 所代表课程的是否可以在一个学期内学完（对于当前要学的所有课程的学时进行标记，若有重复标记则不可能在一学期学完），f[s] 维护学完当前课程所花费的最少学期，枚举子集进行转移。
答案的状态应该是所有课全部修完，即 $f[(1<<n)-1]$。时间复杂度 $O(2^n m n)$。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 15;
int n, m, sum, f[N], g[N], b[20], a[20][105], vis[105];

bool check(int x) {
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i < n; i++) {
    if (x >> i & 1) {
      for (int j = 1; j <= b[i]; j++) {
        if (vis[a[i][j]]) return false;
        vis[a[i][j]] = 1;
      }
    }
  }
  return true;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    for (int j = 1; j <= b[i]; j++) cin >> a[i][j];
  }
  memset(f, 0x3f, sizeof(f));    // 因为要维护最小值，因此初值赋为最大值
  f[0] = 0;                  //  学完 0 门课需要 0 个学期
  sum = (1 << n) - 1;        //  每门课代表一个二进制位，枚举所有可能共有 1<<n 种
  for (int s = 0; s <= sum; ++s) {       
    g[s] = check(s);         // 验证 s 是否能在一个学期内学完
    for (int t = s; t; t = (t - 1) & s)         // 从之前的状态（子集）进行转移
      if (g[t]) f[s] = min(f[s], f[s ^ t] + 1);      // 可以在一个学期学完，则维护最小值
  }
  cout << f[sum] << '\n';
  return 0;
}