Bzoj1933 [Shoi2007]Bookcase 书柜的尺寸

朱雀 2021-12-17 15:55 170阅读 0赞

Time Limit: 5 Sec Memory Limit: 64 MB  
Submit: 554 Solved: 212

## Description ##

Tom不喜欢那种一字长龙式的大书架，他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面，这样需要查书的时候就可以不用起身离开了。显然，这种书柜不能太大，Tom希望它的体积越小越好。另外，出于他的审美要求，他只想要一个三层的书柜。为了物尽其用，Tom规定每层必须至少放一本书。现在的问题是，Tom怎么分配他的工具书，才能让木匠造出最小的书柜来呢？ Tom很快意识到这是一个数学问题。每本书都有自己的高度hi和厚度ti。我们需要求的是一个分配方案，也就是要求把所有的书分配在S1、S2和S3三个非空集合里面的一个，不重复也不遗漏，那么，很明显，书柜正面表面积（S）的计算公式就是： ![1933.jpg][] 由于书柜的深度是固定的（显然，它应该等于那本最宽的书的长度），所以要求书柜的体积最小就是要求S最小。Tom离答案只有一步之遥了。不过很遗憾，Tom并不擅长于编程，于是他邀请你来帮助他解决这个问题。

## Input ##

文件的第一行只有一个整数n（3≤n≤70），代表书本的本数。接下来有n行，每行有两个整数hi和ti，代表每本书的高度和厚度，我们保证150≤hi≤300，5≤ti≤30。

## Output ##

只有一行，即输出最小的S。

## Sample Input ##

4  
220 29  
195 20  
200 9  
180 30

## Sample Output ##

18000

## HINT ##

## Source ##

[Day2][]

动态规划

看上去并不卡时间而是卡空间？

f\[当前处理的书i\]\[第一层宽度j\]\[第二层宽度k\]\[第三层宽度l\]=总高度

发现宽度前缀和-j-k可以算出第三层宽度l，那么这一维可以去掉。第一维可以滚动优化去掉。现在空间够用了。

将书本按高度从大到小排序，发现只有在某一层第一次放书时需要累加高度。

注意每一层至少放一本书。←看漏这个条件，调了好久

1 /*by SilverN*/
     2 #include<algorithm>
     3 #include<iostream>
     4 #include<cstring>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<vector>
     8 using namespace std;
     9 const int mxn=105;
    10 int read(){
    11     int x=0,f=1;char ch=getchar();
    12     while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;ch=getchar();}
    13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    14     return x*f;
    15 }
    16 int f[2][2110][2110];
    17 int smm[mxn];
    18 struct node{
    19     int h,t;
    20 }a[mxn];
    21 int cmp(node a,node b){
    22     return a.h>b.h;
    23 }
    24 int n;
    25 void solve(){
    26     memset(f,0x3f,sizeof f);
    27     int i,j,k;
    28     int tmp=1,nxt=0;
    29     f[0][0][0]=0;
    30     for(i=1;i<=n;i++){
        //枚举书本 
    31         tmp^=1;
    32         nxt^=1;
    33         memset(f[nxt],0x3f,sizeof f[nxt]);
    34         for(j=smm[i-1];j>=0;j--){
    35             for(k=smm[i-1]-j;k>=0;k--){
    36                 if(f[tmp][j][k]==0x3f3f3f3f)continue;
    37                 if(j+k>smm[i-1])break;
    38                 if(!j)f[nxt][j+a[i].t][k]=min(f[nxt][j+a[i].t][k],f[tmp][j][k]+a[i].h);
    39                 else f[nxt][j+a[i].t][k]=min(f[nxt][j+a[i].t][k],f[tmp][j][k]); 
    40                 //
    41                 if(!k)f[nxt][j][k+a[i].t]=min(f[nxt][j][k+a[i].t],f[tmp][j][k]+a[i].h);
    42                 else f[nxt][j][k+a[i].t]=min(f[nxt][j][k+a[i].t],f[tmp][j][k]);
    43                 //
    44                 if(j+k==smm[i-1])
    45                     f[nxt][j][k]=min(f[nxt][j][k],f[tmp][j][k]+a[i].h);
    46                 else
    47                     f[nxt][j][k]=min(f[nxt][j][k],f[tmp][j][k]);
    48             }
    49         }
    50  
    51     }
    52     int ans=0x3f3f3f3f;
    53     for(j=1;j<=smm[n];j++){
    54         for(k=smm[n]-j;k;k--){
    55             if(f[nxt][j][k]>=0x3f3f3f3f || j+k>=smm[n])continue;
    56             ans=min(ans,max(j,max(k,smm[n]-j-k))*f[nxt][j][k]);
    57         }
    58     }
    59     printf("%d\n",ans);
    60     return;
    61 }
    62 int main(){
    63     int i,j;
    64     n=read();
    65     for(i=1;i<=n;i++){
    66         a[i].h=read();
    67         a[i].t=read();
    68     }
    69     sort(a+1,a+n+1,cmp);
    70     for(i=1;i<=n;i++)smm[i]=smm[i-1]+a[i].t;
    71     solve();
    72     return 0;
    73 }

转载于:https://www.cnblogs.com/SilverNebula/p/6509888.html

[1933.jpg]: http://www.lydsy.com/JudgeOnline/images/1933.jpg
[Day2]: http://www.lydsy.com/JudgeOnline/problemset.php?search=Day2