#9#10 WA求助
  • 板块P1504 积木城堡
  • 楼主233L
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/3/8 20:18
  • 上次更新2023/11/5 02:17:36
查看原帖
#9#10 WA求助
405894
233L楼主2021/3/8 20:18

代码里有注释 求大佬帮忙看下

#include<bits/stdc++.h>
using namespace std;
short n,x,h=0xFFF,a;
//x记录城堡能达到的最高高度
//h记录每座城堡都能达到的最高高度(答案的最大可能 
short w[101][10001];
//w[i][0]存储第i座城堡的积木块数
//w[i][j](j!=0)存储第i座城堡第j块积木的棱长 
bool f[10001]={1},ans[10001];
//f用于背包 f[i]=1为能刚好填满高度为i的城堡 
//ans将每座城堡的f做&运算 只有每座城堡都满足的高度才有可能成为答案 
int main()
{
	memset(ans,true,sizeof(ans));
	cin>>n;
	for(short i=1;i<=n;i++)
	{
		for(short j=1;;j++)
		{
			cin>>w[i][j];
			if(w[i][j]<0)break;
			w[i][0]++;//记录第i座城堡积木的块数 
			x+=w[i][j];//记录第i座城堡的高度 
		}
		h=min(h,x),x=0;//求出每座城堡都能达到的最大高度 
	}
	for(short lol=1;lol<=n;lol++)//最外层循环为每座城堡 
	{
		//背包 
		for(short i=1;i<=w[lol][0];i++)
			for(short j=h;j>=w[lol][i];j--)
				f[j]=(f[j]|f[j-w[lol][i]]);
		//进行&运算 
		for(short i=1;i<=h;i++)
		{
			ans[i]=(ans[i]&f[i]);
			f[i]=0;
			if(ans[i])a=i;//当该循环结束时a为答案的最大可能
		}
		h=a,a=0;//因此背包只需搜索到a 
	}
	cout<<h;
}

2021/3/8 20:18
加载中...