# 洛谷 P3112 [USACO14DEC]后卫马克Guard Mark【状压DP】【枚举】

$N\le 20$的状态怎么着也想一想状压吧

## 题目描述

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的高度，那牛们将抢到飞盘。

## 输入输出格式

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.

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).

4 10
9 4 1
3 3 5
5 5 10
4 4 5

2

## 题解：

其实这题贪心也可做，不过感觉推理不严谨或者推错，并且状压DP的确好写一点。

二进制枚举有一个性质，就是对于当前枚举到的数，它的子集一定被枚举过，因为它代表的数总大于它的真子集，因此我们可以在枚举的时候用填表法，转移它的每个1，f[i]存的是二进制状态1下最大承重量，这样状态就即全又合法了。

因为每个二进制数对应一个方案，所以可以在枚举时把方案中的1的高度全部累加，如果高度和大于H，就与ans比大小更新。如自始至终都没有任何一个更新，那么就输出无解。

要注意一点就是有的状态可能不合法，也就是从它的底层就开始不合法，因此上面更新不到状态，也是无解状态的一个来源。

## Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
long long f[(1<<20)+(1<<10)];
long long w[22],h[22],p[22];
int main()
{
memset(f,-1,sizeof(f));
int n,flag=0;
long long H,ans=0;
scanf("%d%lld",&n,&H);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&h[i],&w[i],&p[i]);
f[0]=0x3fffffffffffffff;
for(int i=1;i<(1<<n);i++)
{
long long t=0;
int k=i,u=0;
while(k)
{
u++;
if(k&1)
t+=h[u];
k>>=1;
}
for(int j=1;j<=n;j++)
if(i&(1<<j-1))
{
k=i^(1<<j-1);
if(f[k]>=w[j])
f[i]=max(f[i],min(f[k]-w[j],p[j]));
}
if(t>=H&&~f[i])//同时注意f是否合法
{
ans=ans>f[i]?ans:f[i];
flag=1;
}
}
if(!flag)
puts("Mark is too tall");
else
printf("%lld\n",ans);
return 0;
}

Subscribe

/* */