P3112 【[USACO14DEC]后卫马克Guard Mark】

communist · 2018-09-14 20:53:59 · 题解

看到没有完整的贪心题解，本蒟蒻决定来补充一发（没有完整证明的贪心是不圆满的）

不知道大家做过NOIP2012国王游戏没，这两道题思路相似

进入正题，看着就像贪心的一道题

怎么贪，按height,strength,weight排序好像都不合适

试图分析相邻两项交换的影响

一个\text{\red{位置}}的承重量可以这样表示Rest_i=Strength_i-\sum{Weight_j}(j>i)

同理，它的下一项可以如下表示Rest_{i+1}=Strength_{i+1}-\sum{Weight_j}(j>i+1)

相邻两项交换后是这样的

我们要使稳定强度最大，即最大化Min(Rest_i)

还是考虑这相邻两项，我们考虑是否交换就转化为了判断这个东西

为了简化式子

我们给上述每项同加\sum{Weight_j}(j>i+1)

上式化简为

观察到

如果

那么Next中min的一定是Strength_{i+1}-Weight_i，而Pre中每一项都大于它，即交换前总优于交换后

反之，交换后优于交换前

移项得，

时，交换前更优

所以我们按照Strength+Weight从大到小排序即可

然后2^n枚举选择哪些牛，对于每种情况，求出Rest的最小值，然后在其中取最大即可

上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int h,w,s;
}a[30];
int n,h;
bool c[30];
long long ans=-1;
bool cmp(const node &x,const node &y)
{
    return x.w+x.s>y.w+y.s;
}
void dfs(int x,int ch)
{
    c[x]=ch;
    if(x==n)
    {
        long long tmp=1e9,len=0;
        for(int i=1;i<=n;i++)
            if(c[i])
            {
                len+=a[i].h;
                long long sum=0;
                for(int j=i+1;j<=n;j++)
                    sum+=c[j]?a[j].w:0;
                tmp=min(tmp,a[i].s-sum);
            }
        if(len>=h)
            ans=max(ans,tmp);
        return;
    }
    dfs(x+1,1);
    dfs(x+1,0);
}
int main()
{
    scanf("%d%d",&n,&h);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].h,&a[i].w,&a[i].s);
    sort(a+1,a+n+1,cmp);
    dfs(0,0);

    if(ans==-1)
        printf("Mark is too tall\n");
    else
        printf("%lld\n",ans);
    return 0;
}