---

题目传送门

---

前言

虽然是一道比较好想的状压 $dp$，但是它深深使我我感受到【简洁而快速的二进制操作】对状压 $dp$ 的重要意义。

---

暴力思路 & 代码

设 $d{p}_s$ 为表示：状态 $s$ 所代表的人们过桥所需的最少时间（$s$ 的二进制中，从右往左数第 $i$ 若为 $1$，那么就代表这个人在过桥队伍当中；若为 $0$，就代表不在这一波过桥）。
最后的答案是 $d{p}_{(1<<n)-1}$（即二进制上的每一位都是 $1$）。

我们先预处理每种状态的总重与过桥时间。
然后从小到大枚举状态 $i$，再枚举状态 $i$ 的子状态 $j$（子状态就是指：【$s$ 所代表过桥的人组成的集合】的子集），然后看子状态 $j$ 的总重是否能过桥，能的话就转移，不能的话就算了。
具体见代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 16 + 7;
const int maxs = (1 << 16) + 7;
const int inf  = 0x3f3f3f3f;

int n, m, ns;
int w[maxn], t[maxn];
int sw[maxs], mt[maxs];

int dp[maxs];
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", t + i, w + i);
	ns = (1 << n) - 1;
	for (int s = 0; s <= ns; ++s)
		for (int i = 0; i < n; ++i)
			if (s & (1 << i))
				sw[s] += w[i + 1],
				mt[s] = max(mt[s], t[i + 1]);
				
	memset(dp, inf, sizeof(dp));
	dp[0] = 0;
	for (int i = 0; i <= ns; ++i) {
		for (int j = 0; j <= ns; ++j) {
			if (i & j != j) continue;  // 这一步就是用来判断 j 是否是 i 的子状态的
			if (sw[j] <= m) dp[i] = min(dp[i], mt[j] + dp[i ^ j]);
		}
	}
	printf("%d\n", dp[ns]);
	return 0;
}

时间复杂度是 $O(2^n\times 2^n)$ 跑满的，交上去只能得 $85pts$。

---

优化

说是优化，其实就是舍去一些不必要的状态（即：$j$ 不是 $i$ 子状态的情况），并不能优化时间复杂度，但是确实可以通过此题，因为时间复杂度远远跑不满。

先看看改了哪里：

for (int j = i; j; j = i & (j - 1))

其实就是改了枚举 $i$ 的子状态的方法，即：不再枚举所有状态然后判断哪个是子状态，而是直接枚举子状态。

这个的妙处在于，它每次都会把 $j$ 目前的最后一个 $1$ 变成 $0$，然后再把这位之前的变成与 $i$ 对应位置相同的状态。
比如：
$$i=01101100,j_0=i=01101100$$
下边开始进行模拟运算：
$$\begin{gathered} j_1=i\&(j_0-1)=01101000 \\ {j}_2=i\&(j_1-1)=01100100 \\ {j}_3=i\&(j_2-1)=01100000 \\ {j}_4=i\&(j_3-1)=01001100 \\ {j}_5=i\&(j_4-1)=01001000 \\ {j}_6=i\&(j_5-1)=01000100 \\ {j}_7=i\&(j_6-1)=01000000 \\ {j}_8=i\&(j_7-1)=00101100 \\ {j}_9=i\&(j_8-1)=00101000 \\ {j}_{10}=i\&(j_9-1)=00100100 \\ {j}_{11}=i\&(j_{10}-1)=00100000 \\ ... \end{gathered}$$
所以它是正确的。
代码就不全放了。