CF294B Shaass and Bookshelf 题解

题目链接：CF294B Shaass and Bookshelf

题意：Shaass has n n n books. He wants to make a bookshelf for all his books. He wants the bookshelf’s dimensions to be as small as possible. The thickness of the i i i -th book is t i t_{i} ti​ and its pages’ width is equal to w i w_{i} wi​ . The thickness of each book is either 1 1 1 or 2 2 2 . All books have the same page heights.

Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.

Help Shaass to find the minimum total thickness of the vertical books.

1 ≤ n ≤ 100 , 1 ≤ t i ≤ 2 , 1 ≤ w i ≤ 100 1le n le 100,1 le t_i le 2,1 le w_i le 100 1≤n≤100,1≤ti​≤2,1≤wi​≤100

翻译一下就是说要求竖直摆放时厚度和 ∑ t i sum t_i ∑ti​ 最小，同时不竖直摆放的书的宽度和 ∑ w i sum w_i ∑wi​ 不超过厚度和 ∑ t i sum t_i ∑ti​，高度均相等

注意到这个厚度很小，因此我们可以枚举一下厚度和

然后问题就转化为了，厚度和为 j j j ，要求竖直摆放的那些书宽度和尽可能的大（这样放在上面的宽度和就小了）

于是就转化为了恰好装满的01背包问题

时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码：

#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(305)

int n;
int w[N],v[N],sumw,sumv,dp[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> w[i] >> v[i];
        sumw+=w[i];sumv+=v[i];
    }
    memset(dp,0xc0,sizeof(dp));
    dp[0]=0;
    for(int i=1; i<=n; i++)
        for(int j=sumw; j>=w[i]; j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    for(int i=1; i<=sumw; i++)
    {
        if(sumv-dp[i]<=i)
        {
            cout << i;
            return 0;
        }
    }
    return 0;
}

转载请说明出处