题解 P2677 【超级书架 2】

道费而隐 · 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;//结束
}

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