[USACO 2014 Gold] Guard Mark

作法：

對於一個用牛疊成的塔，我們定義他的強度為：min{ 牛的強度 - 牛的實際負重 }，如果強度 >= 0 代表這座塔能夠疊起來，那麼只要DP出每個牛集合形成的塔最大強度是多少就可以了，每次枚舉哪隻牛當最底下的，那麼因為剩下的牛就是這個集合扣掉這隻牛，所以這隻牛的負重也確定了，就可以轉移到比較小的問題。

code :

#include<bits/stdc++.h>
#define INF (1LL<<60)
#define LL long long
using namespace std;
const int maxn=20+1 ;
 
LL dp[1<<maxn] ;
int h[maxn],w[maxn],str[maxn] ;
LL hsum[1<<maxn],wsum[1<<maxn] ;
 
main()
{
    if(fopen("guard.in","r"))
    {
        freopen("guard.in","r",stdin) ;
        freopen("guard.out","w",stdout) ;
    }
    int n,H ; scanf("%d%d",&n,&H) ;
    for(int i=0;i<n;i++) scanf("%d%d%d",&h[i],&w[i],&str[i]) ;
 
    dp[0]=INF ;
    LL ans=-INF ;
    for(int i=1;i<(1<<n);i++)
    {
        dp[i]=-INF ;
        for(int j=0;j<n;j++) if(i&(1<<j))
        {
            wsum[i]+=w[j] ;
            hsum[i]+=h[j] ;
            dp[i]=max(dp[i],
            min(str[j]-wsum[i^(1<<j)],dp[i^(1<<j)])) ;
        }
        if(hsum[i]>=H) ans=max(ans,dp[i]) ;
    }
    if(ans<0) printf("Mark is too tall\n") ;
    else printf("%lld\n",ans) ;
}