M_sea

UVa12099 The Bookcase
UVaLuogu分析设 $dp_{i,j,k}$ 表示前 $i$ 本书,第一层宽度为 $j$ ,第二层宽度为 $k...
扫描右侧二维码阅读全文
07
2019/08

UVa12099 The Bookcase

UVa

Luogu

分析

设 $dp_{i,j,k}$ 表示前 $i$ 本书,第一层宽度为 $j$ ,第二层宽度为 $k$ 时,第二三层的高度的最小值。

转移直接枚举放在哪一层即可。

然而有个问题,我们并不知道某一层原来的高度。所以我们先把所有书按高度从大到小排序。

边界就是 $dp_{1,0,0}=0$ ,此时我们强制第一本书放在了第一层,这样子不影响答案而且方便 DP 。

一些优化:第一维滚动数组;$j$ 和 $k$ 的上界设为前 $i$ 本书的宽度之和。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=70+10,L=2100+10;
const int inf=0x3f3f3f3f;

int n,sum[N];
struct book { int h,w; } a[N];
bool operator <(book a,book b) { return a.h>b.h; }
int dp[2][L][L];

int main() {
    int T=read();
    while (T--) {
        n=read();
        for (re int i=1;i<=n;++i) a[i].h=read(),a[i].w=read();
        sort(a+1,a+n+1);
        for (re int i=2;i<=n;++i) sum[i]=sum[i-1]+a[i].w;
        dp[1][0][0]=0;
        for (re int i=1;i<n;++i) {
            int now=i&1,nxt=now^1;
            for (re int j=0;j<=sum[i+1];++j)
                for (re int k=0;j+k<=sum[i+1];++k)
                    dp[nxt][j][k]=inf;
            for (re int j=0;j<=sum[i];++j)
                for (re int k=0;j+k<=sum[i];++k) {
                    if (dp[now][j][k]==inf) continue;
                    chkmin(dp[nxt][j][k],dp[now][j][k]);
                    if (!j) chkmin(dp[nxt][a[i+1].w][k],dp[now][j][k]+a[i+1].h);
                    else chkmin(dp[nxt][j+a[i+1].w][k],dp[now][j][k]);
                    if (!k) chkmin(dp[nxt][j][a[i+1].w],dp[now][j][k]+a[i+1].h);
                    else chkmin(dp[nxt][j][k+a[i+1].w],dp[now][j][k]);
                }
        }
        int ans=inf;
        for (re int i=1;i<=sum[n];++i)
            for (re int j=1;i+j<=sum[n];++j) {
                if (dp[n&1][i][j]==inf) continue;
                chkmin(ans,(dp[n&1][i][j]+a[1].h)*max(max(i,j),sum[n]-i-j+a[1].w));
            }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 08 月 07 日 04 : 58 PM

发表评论