UVA 12099 The Bookcase(dp)

叁歲伎倆 2021-12-16 13:45 138阅读 0赞

## 题意：   有N本书，第i本书有一个高度Hi和宽度Wi，现要求构建一个三层的书架，你必须把所有书放在书架上。设三层高度（该层最高的书的高度）之和为h，书架总宽度（即每层总宽度的最大值）为w，要求h×w尽可能小。 ##

## 思路（抄自紫书）：   首先我们可以考虑将所有书按高度从大到小排序。不妨设最高的书在第1层，且第二层的高度大于等于第三层的高度。 ##

## 则我们可以定义状态d(i,j,k)为当前已经安排了i本书，第二层的宽度为j，第三层的宽度为k时第二层和第三层的高度之和。 ##

## 为什么不记录第一层的高度？因为最高的书在第一层，即这一层的书永远都不会比它更高了。 ##

## 为什么不记录第一层的宽度？因为目前三层的书的总宽度为前ii本书的总宽度，所以只要知道了第二、第三层的宽度，就知道了第一层的宽度。 ##

## 另外，因为这些书已经从大到小排了序，所以，一旦三层都放了书，则书架的总高度就已经确定了。 ##

## 综上，我们可以得到以下两点： ##

## 若只有第一、第二层放了书，则当且仅当往第三层放书ii时，第三层的高度会变为Hi；   若只有第一层放了书，则当且仅当第二层放书ii时，第二层的高度会变为Hi。   所以我们采用刷表法进行转移。 ##

## 将书i放在第一层：用d(i,j,k)更新d(i+1,j,k)，因为第一层的高度不变。 ##

## 将书i放在第二层：用d(i,j,k)+f(j,Hi)更新d(i+1,j+Wi,k)。 ##

## 将书i放在第三层：用d(i,j,k)+f(k,Hi)更新d(i+1,j,k+Wi)。 ##

## 其中：f(j,Hi)当且仅当j=0时等于Hi，否则等于0。 ##

## 注意：由于状态数量很大（70×2100×2100），所以我们必须采用滚动数组进行递推。 ##

## LRJ代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 70 + 5;
    const int maxw = 30;
    const int INF = 1000000000;
    struct Book {
      int h, w;
      bool operator < (const Book& rhs) const {
        return h > rhs.h || (h == rhs.h && w > rhs.w);
      }
    } books[maxn];
    // We sort books in decreasing order of heights and place them one by one
    // So level 1's height is book 1's height
    // dp[i][j][k] is the minimal total heights of level 2 and 3 when we used i books, level 2 and 3's total widths are j and k,
    // level 1's width is (sumw[n] - j - k)
    int dp[2][maxn*maxw][maxn*maxw];
    int sumw[maxn]; // sum[i] is the sum of widths of first i books. sum[0] = 0.
    // increased height if you place a book with height h to a level with width w
    // if w == 0, that means the level if empty, so height is increased by h
    // otherwise, the height is unchanged because we're adding books in decreasing order of height
    inline int f(int w, int h) {
      return w == 0 ? h : 0;
    }
    
    inline void update(int& newd, int d) {
      if(newd < 0 || d < newd) newd = d;
    }
    
    int main () {
      int T;
      scanf("%d", &T);
      while(T--) {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
          scanf("%d%d", &books[i].h, &books[i].w);
        sort(books, books+n);
        sumw[0] = 0;
        for(int i = 1; i <= n; i++)
          sumw[i] = sumw[i-1] + books[i-1].w;
        dp[0][0][0] = 0;
        int t = 0;
        for(int i = 0; i < n; i++) {
          // Don't use memset. It's too slow
          for(int j = 0; j <= sumw[i+1]; j++)
            for(int k = 0; k <= sumw[i+1]-j; k++) dp[t^1][j][k] = -1;
            
          for(int j = 0; j <= sumw[i]; j++)
            for(int k = 0; k <= sumw[i]-j; k++) if(dp[t][j][k] >= 0) {
              update(dp[t^1][j][k], dp[t][j][k]); /// level 1
              update(dp[t^1][j+books[i].w][k], dp[t][j][k] + f(j,books[i].h)); /// level 2
              update(dp[t^1][j][k+books[i].w], dp[t][j][k] + f(k,books[i].h)); /// level 3
            }
          t ^= 1;
        }
        int ans = INF;
        for(int j = 1; j <= sumw[n]; j++) // each level has at least one book
          for(int k = 1; k <= sumw[n]-j; k++) if(dp[t][j][k] >= 0) {
            int w = max(max(j, k), sumw[n]-j-k);
            int h = books[0].h + dp[t][j][k];
            ans = min(ans, w * h);
          }
        printf("%d\n", ans);
      }
      return 0;
    }