[luogu] P1504 积木城堡 01背包

前言

有点抽象(😅

传送门 :

思路

一开始以为可以每一组都求一个最小值,最后最小值就是答案 ( 但是题目没怎么清楚

所以最后还是选择用 01 01 01背包来做了

为什么我们可以使用 01 01 01背包呢 ?

其实,对于每组里面的方块 无非就是拿和不拿的区别

因此我们可以使用 01 01 01背包处理出来,所有的高度方案

然后在通过可达的高度来贡献答案

最后我们只需要倒序的判断答案即可

CODE

void init()
{
	memset(f,0,sizeof f);
	h = 0 ,cnt =0  ;
	
}
void solve()
{
	int n;cin>>n;
	for(int i=1;i>x;if(x ==-1)break;
			w[++cnt] =  x;
			h+=x;	
		}
		
		f[0] = 1;
		
		
		for(int i=1;i=w[i];j -- )
			{
				f[j]|=f[j-w[i]];
			}
		}
		
		minn = min(minn,h);
		for(int i = 1;i=1;i -- )
	{
		if(ans[i] == n)
		{
			cout