自动搬运

查看原文

来自洛谷，原作者为

	道费而隐 **

搬运于2025-08-24 21:40:21，当前版本为作者最后更新于2018-07-03 11:37:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

DP题解

各位大佬们都用的深搜啊...

其实dp也可以解这道题，而且是裸的01背包
我们可以先算出牛的总高度，再减去书架的高度，即为背包的总容量。要使得叠出的塔在高度不小于书架高度的情况下，高度尽可能小，那么背包就应尽可能地填满，所以h[i]既相当于01背包里的容量又相当于价值，使背包中总价值最大，那么背包中总容量（高度）就最大，此时剩下的牛叠出的塔在高度不小于书架高度的情况下，高度就是最小的。
因此，状态转移方程如下：

f[j]=max(f[j],f[j-h[i]]+h[i])

上AC代码：

#include<vector>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<string>
#include<iomanip>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<queue>
#include<map>
#include<set> 
//不想打万能头文件
using namespace std;
typedef long long ll;
int n,b,tot,w,h[25],f[1000001];
int main()
{
	cin>>n>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		tot+=h[i];//求牛的总高度
	}
	w=tot-b;//w即为所以牛的高度减去书架的高度，也就是背包的容量
	for(int i=1;i<=n;i++)
	{
		for(int j=w;j>=h[i];j--)
		{
			f[j]=max(f[j],f[j-h[i]]+h[i]);//h[i]既相当于01背包里的容量又相当于价值
		}
	}
	cout<<tot-f[w]-b;//牛的总高度减去放入背包中牛的高度再减去书架高度就是所求解
	return 0;//结束
}

本蒟蒻第一次发题解，一定要过啊。。