Description：

$N$ 头牛每头牛有自己的高度，自身重量及承受重量。 选出一些牛来叠成一堆。问是否可以到一个高度为 $H$ 的值。如果能到最大化还可以在上面继续放的重量。

$1\le n \le 20$

Solution：

做法一：贪心。

按照 $w+s$ 排序按从大到小的顺序叠放， $dfs$ 枚举 $2^n$ 种方案再 $check$ 。

证明：设叠的重量前缀和为 $W$ ，第一种方案最终的结果是 $\min(s_1-W-w_2,s_2-W)$ ，第二种方案最终结果是 $\min(s_2-W-w_1,s_1-W)$ ，因为 $s_1+w_1>s_2+w_2$ ，所以 $s_1-W-w_2>s_2-W-w_1$ ，。

口胡没有代码。

做法二：状压 $DP$ 。

设 $f[S]$ 表示当选的牛的集合为 $S$ 时的最大承受重量，因为集合已知所以高度也可以计算，那么转移为 $f[S\cup \{i\}]=\max(\min(f[S]-w[i],s[i]))$ ，相当于每次把新加的牛放在最上面。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 21

int h[MAXN],w[MAXN],s[MAXN];

int f[1 << MAXN],g[1 << MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int sum = 0;

	for(int i = 1;i <= n;++i)scanf("%d%d%d",&h[i],&w[i],&s[i]);

	for(int i = 1;i <= n;++i)sum += h[i];

	int tot = (1 << n) - 1;

	int ans = -1;

	f[0] = 0x3f3f3f3f;

	for(int b = 0;b <= tot;++b)

	{

		for(int i = 1;i <= n;++i)

		{

			if(!(b & (1 << (i - 1))))

			{

				if(f[b] >= w[i])

				{

					f[b | (1 << (i - 1))] = max(f[b | (1 << (i - 1))],min(f[b] - w[i],s[i]));

					g[b | (1 << (i - 1))] = g[b] + h[i];

				}

			}

		}

		if(b != 0 && g[b] >= m)ans = max(ans,f[b]);

	}

	if(ans == -1)puts("Mark is too tall");

	else cout << ans << endl;

	return 0;

}