UVA - 12099 The Bookcase（01背包问题+优化）

链接

紫书没有提到的是，这三个书架都是非空的

容易知道，高度最大的那本书一定是某层的高度，那么我们假设它在第一层。因为某一层的高度是取所有书的 m a x ( H ) max(H) max(H)而宽度是 s u m ( d ) sum(d) sum(d)，因为这层书的高度是不容易转移的，但是宽度之和却容易转移，那么将宽度和作为决策的一部分状态

状态转移

设 d ( i , j , k ) d(i,j,k) d(i,j,k)表示安排完前 i i i本书，第二层的宽度之和为 j j j，第三层的宽度之和为 k k k时，第二层和第三层高度和的最小值。当然将书按高度从大到小排序，假设第一层的高度大于等于第二层高度，第二层高度大于等于第三层高度，这样方便转移

因为第一层的书的高度已经确定，而第一层的宽度可以考虑由当前考虑的前 i i i本书的宽度之和 w [ i ] w[i] w[i]减去第二层和第三层的宽度和

具体的状态转移参考紫书

边界和答案

边界为 d [ 1 ] [ 0 ] [ 0 ] = 0 d[1][0][0]=0 d[1][0][0]=0，其余为 i n f inf inf

最终的答案是 d [ n & 1 ] [ i ] [ j ] , 1 ≤ i ≤ w [ n ] , 1 ≤ j ≤ w [ n ] d[n\&1][i][j],1 \leq i \leq w[n],1 \leq j \leq w[n] d[n&1][i][j],1≤i≤w[n],1≤j≤w[n]，因为使用了滚动数组

优化

使用滚动数组，只需考虑上次的状态和这次的状态，那么使用位运算代替取模节省时间

此外，LRJ老师提到的那些： j + k j+k j+k不应该超过当前宽度和 w [ i ] w[i] w[i]；假设第 i i i层的总宽度为 W i W_i Wi​，如果 W 2 > W 1 + 30 W_2>W_1+30 W2​>W1​[phone]是一本书的宽度上限），那么可以将第二层的这本书放到第一层，对答案无影响。同理第三层和第二层，那么只需计算 W 2 ≤ W 1 + 30 W_2 \leq W_1+30 W2​≤W1​+30和 W 3 ≤ W 2 + 30 W_3 \leq W_2+30 W3​≤W2​+30的状态

本题写刷表法更简单，写填表法会稍微麻烦

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

struct node{
    int h,w;

    bool operator < (const node &p) const {
        return h>p.h;
    }
}a[105];

int w[105];
int d[2][2200][2200];

int f(int x,int y){
    return x==0?y:0;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].h>>a[i].w;
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            w[i]=w[i-1]+a[i].w;
        }
        memset(d,inf,sizeof d);
        d[1][0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=w[n];j++) if(j<=w[i])
                for(int k=0;k<=w[n];k++) if(j+k<=w[i] && j<=w[i]-j-k+30 && k<=j+30){
                    int now=i&1,nxt=now^1;
                    d[nxt][j][k]=min(d[nxt][j][k],d[now][j][k]);

                    if(!j) d[nxt][a[i+1].w][k]=min(d[nxt][a[i+1].w][k],d[now][j][k]+a[i+1].h);
                    else d[nxt][j+a[i+1].w][k]=min(d[nxt][j+a[i+1].w][k],d[now][j][k]);

                    if(!k) d[nxt][j][a[i+1].w]=min(d[nxt][j][a[i+1].w],d[now][j][k]+a[i+1].h);
                    else d[nxt][j][k+a[i+1].w]=min(d[nxt][j][k+a[i+1].w],d[now][j][k]);
                }
        }

        int ans=inf;
        int H=a[1].h;
        for(int i=1;i<=w[n];i++)
            for(int j=1;j<=w[n];j++) if(d[n&1][i][j]<=900){
                ans=min(ans,(H+d[n&1][i][j])*max(max(i,j),w[n]-i-j));
            }
        cout<<ans<<endl;

    }
    return 0;
}