题目大意

有 $n$ 头牛坐电梯，重量分别为 $c_i$，电梯的最大限额是 $W$，求最少分多少次能够全部上去。

分析

注意 $n \leqslant 18$，枚举全排列是不行的。考虑用状态压缩，将第 $j$ 头奶牛的选和不选用状态 $i$ 的第 $j$ 位数字表示。设 $f_i$ 表示状态为 $i$ 时最小乘电梯次数，$g_i$ 表示此状态下最新那个电梯已经有的重量。

  • 首先令 cow = i << (j - 1)，若 i & cow 为 $1$ 则说明这个奶牛已经坐上电梯了，不计算。
  • 当 $W - g_i \geqslant c_i$ 时，最后那个电梯坐的下这头牛。
  • 当 $W - g_i < c_i$ 时，只能新开一个电梯。

还是代码更清晰

const int maxn = 18;

ll ci[maxn];
ll ff[1 << maxn], gg[1 << maxn];

int main() {
	ll n = rr(), W = rr();
	for (int i = 1; i <= n; i++)
		ci[i] = rr();

	fill_n(ff, 1 << maxn, n);
	fill_n(gg, 1 << maxn, W);
	ff[0] = 1, gg[0] = 0;

	for (int i = 0; i < (1 << n); i++) {
		for (int j = 1; j <= n; j++) {
			ll cow = 1 << (j - 1);
			if (i & cow)
				continue;
			if (W - gg[i] >= ci[j]) {
				ff[i | cow] = ff[i];
				gg[i | cow] = min(gg[i | cow], gg[i] + ci[j]);
			} else if (W - gg[i] < ci[j] && ff[i | cow] >= ff[i] + 1) {
				ff[i | cow] = ff[i] + 1;
				gg[i | cow] = min(gg[i | cow], ci[j]);
			}
		}
	}
	printf("%lld", ff[(1 << n) - 1]);
	return 0;
}