bzoj 3824: [Usaco2014 Dec]Guard Mark【状压dp】

设f[s]为已经从上到下叠了状态为s的牛的最大稳定度，转移的话枚举没有在集合里并且强壮度>=当前集合牛重量和的用min(f[s],当前放进去的牛还能承受多种)来更新，高度的话直接看是否有合法集合的高度达到要求即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=25;

int n,m,h[N],w[N],a[N],f[2000005],ans=-1;

int main()

{

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

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

		scanf("%d%d%d",&h[i],&w[i],&a[i]);

	for(int i=0,len=(1<<n)-1;i<=len;i++)

		f[i]=-1;

	f[0]=1e9;

	for(int s=0,len=(1<<n)-1;s<=len;s++)

		if(f[s]!=-1)

		{

			int we=0,he=0;

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

				if(s&(1<<(i-1)))

					we+=w[i],he+=h[i];//cerr<<s<<" "<<f[s]<<" "<<we<<" "<<he<<endl;

			if(he>=m)

				ans=max(ans,f[s]);

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

				if(!(s&(1<<(i-1)))&&a[i]>=we)

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

		}

	if(ans==-1)

		puts("Mark is too tall");

	else

		printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 3824: [Usaco2014 Dec]Guard Mark【状压dp】

最新文章

热门文章