Description
Farmer John and his herd are playing frisbee. Bessie throws the frisbee down the field, but it's going straight to Mark the field hand on the other team! Mark has height H (1 <= H <= 1,000,000,000), but there are N cows on Bessie's team gathered around Mark (2 <= N <= 20). They can only catch the frisbee if they can stack up to be at least as high as Mark. Each of the N cows has a height, weight, and strength. A cow's strength indicates the maximum amount of total weight of the cows that can be stacked above her.
Given these constraints, Bessie wants to know if it is possible for her team to build a tall enough stack to catch the frisbee, and if so, what is the maximum safety factor of such a stack. The safety factor of a stack is the amount of weight that can be added to the top of the stack without exceeding any cow's strength.
FJ将飞盘抛向身高为H(1 <= H <= 1,000,000,000)的Mark，但是Mark被N(2 <= N <= 20)头牛包围。牛们可以叠成一个牛塔，如果叠好后的高度大于或者等于Mark的高度，那牛们将抢到飞盘。
每头牛都一个身高，体重和耐力值三个指标。耐力指的是一头牛最大能承受的叠在他上方的牛的重量和。请计算牛们是否能够抢到飞盘。若是可以，请计算牛塔的最大稳定强度，稳定强度是指，在每头牛的耐力都可以承受的前提下，还能够在牛塔最上方添加的最大重量。
Input
The first line of input contains N and H.
The next N lines of input each describe a cow, giving its height, weight, and strength. All are positive integers at most 1 billion.
Output
If Bessie's team can build a stack tall enough to catch the frisbee, please output the maximum achievable safety factor for such a stack. Otherwise output "Mark is too tall" (without the quotes).
Sample Input
4 10
9 4 1
3 3 5
5 5 10
4 4 5Sample Output
2题目分析：
f[s]代表s状态的牛能组成的牛塔最大的耐久力
初始化： f[(1<<(i-1))]=power[i]
转移方程自己看代码吧 反正就是枚举S里的牛 能转移就转移 取个最优解
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long m;
long long w[10000],h[10000],power[10000];
long long f[1<<22];
long long ans=-1;
int main()
{
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&h[i],&w[i],&power[i]);
for(int i=1;i<=n;i++) f[(1<<(i-1))]=power[i];
for(int i=1;i<(1<<n);i++)
{
bool flag=0;
for(int j=1;j<=n;j++)
{
if(i&(1<<(j-1)))
{
if(f[i-(1<<(j-1))]>=w[j])
{
flag=1;
f[i]=max(f[i],min(f[i-(1<<(j-1))]-w[j],power[j]));
}
}
}
long long sum=0;
for(int j=1;j<=n;j++)
if(i&(1<<(j-1))) sum+=h[j];
if(flag==1)
if(sum>=m)
ans=max(ans,f[i]);
}
if(ans==-1) printf("Mark is too tall");
else printf("%lld",ans);
return 0;
}
