状压DP枚举子集类例题

思路

首先数据不大，可以状压，那就将 $f[i]$ 表示 前 $i$ 个人过桥的最小时间， 通常我们可以设置一个断点 $j$, 只需要知道 $j$ 至 $i$ 之间所需要的时间即可，那么转移式有

其中 $i\ xor\ j$ 表示 $i$ 种剩余的子集， 前提是 $j$ 是 $i$ 的子集

这样题目就做完了

如何枚举子集

for (s0=s;s0;s0=(s0-1)&s) 依次枚举 $s$ 的子集

  for （int s=0;s<=mx;s++)
   for （int s0=s;s0;s0=(s0-1)&s)
   

证明

我们枚举一下

当 $s=1010$ 此时 $s_0=1010$

减一得 $s_0=1001$

与$s$ 与得 $s_0=1000$

减一得 $s_0=0111$

与$s$ 与得 $s_0=0010$

减一得 $s_0=0001$

与$s$ 与得 $s_0=0000$

这样我们得到了集合 $s$ 的所有子集 $s_0$ 即$\{11,10,01,00\}$特别神

时间复杂度

那么时间复杂度是什么

$O(3^N)$

推导：对于有着 $k$ 个 $1$ 的二进制数字，枚举子集需要的时间复杂度为 $2^k$ ， 拥有 $k$ 个 $1$ 的数字的数量用组合数学可知：$\dbinom{n}{k}$

那么总的时间复杂度为：$\sum_{k=0}^nC(n,i)\times2^k$

这里给出二项式定理

$(x+y)^n=\sum_{k=0}^n\dbinom{n}{k}\times x^{(n-k)}\times y^k$

我们将这里的 $x$ 默认为 $1$， 则 $y$ 就等于 $2$

那么时间复杂度就为 $(1+3)^n=O(3^n)$

Code

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const int A = 1e5 + 11;
const int B = 16;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int a,b,t[1<<B],w[1<<B],f[1<<B], mt[1<<B], mw[1<<B];

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  cin>>a>>b;
  int mx=(1<<b)-1;
  for (int i=1;i<=b;i++) cin>>t[i]>>w[i];
  for (int i=0;i<=mx;i++)
  {
    for (int j=1;j<=b;j++)
      if(i&(1<<(j-1))){
        mt[i]=max(mt[i], t[j]);
        mw[i]+=w[j];
      }
  }
  memset (f,0x3f,sizeof(f));
  f[0]=0;
  for (int i=0;i<=mx;i++)
  {
    for (int j=i;;j=(j-1)&i)
    {
      if(mw[i^j]<=a) f[i]=min(f[i],f[j]+mt[i^j]);
      if(!j) break;
    }
  }
  cout<<f[mx];
  fclose(stdin);
  fclose(stdout);
  return 0;
}