题目描述

小$A$有$N$本算法书，第$i$本书的高度为$h_i$，厚度为$w_i$。

小$A$想要制造一个三层的矩形书架来放置这些书籍。要求书籍全部正立放进书架。

小$A$想知道能放下这些书籍的书架的表面积最少为多少？

书架的最小表面积等于书架的总高度乘以厚度总和最大的那一层的厚度总和。注意不允许有其中一层高度为$0$.

输入格式

第一行一个正整数$N$

接着$N$行，第$i+1$行两个用空格隔开的正整数为$h_i$和$w_i$

输出格式

一行一个整数，要求见题面描述

输入输出样例

输入 #1 复制

4
150 8
160 7
170 9
150 10

输出 #1 复制

7200

说明/提示

样例解释：

第一层放一、二号书，高度为$\max(160,150)=160$，厚度和为$8+7=15$

第二层放三号书，高度为$170$，厚度和为$9$

第三层放四号书，高度为$150$，厚度和为$10$

书架表面积$=15\times(160+170+150)=7200$

对于$30$%的测试数据，$n\le15$.

对于$100$%的测试数据，$3\le n\le70,150<=\le h_i\le300,5\le i\le30$

（友情提示：时限3s）

---

这道题我是用DFS+剪枝做的，代码如下：

#include<bits/stdc++.h>
#define ll long long
#define landingyu work();
#define AK return
#define IOI 0;
#define inf 0x3f3f3f3f
#define eps 0.00001
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

using namespace std;
struct node{
	int w;
	int h;
}book[75];
int maxw=-inf,ans=inf,n;
inline int max3(int a,int b,int c){return max(max(a,b),c);}
inline void dfs(int level,int ah,int bh,int ch,int aw,int bw,int cw){
	if(level==n+1){
		if(ah && bh && ch) ans=min(ans,max3(aw,bw,cw)*(ah+bh+ch));
		return;
	}
	if(max3(aw,bw,cw)*(ah+bh+ch)>=ans) return;
	dfs(level+1,max(ah,book[level].h),bh,ch,aw+book[level].w,bw,cw);
	dfs(level+1,ah,max(bh,book[level].h),ch,aw,bw+book[level].w,cw);
    dfs(level+1,ah,bh,max(ch,book[level].h),aw,bw,cw+book[level].w);
}
inline void work(){
    n=read();
    for(register int i=1;i<=n;i++) book[i].h=read(),book[i].w=read();
    dfs(1,0,0,0,0,0,0);
    write(ans);
}
int main(){landingyu AK IOI}

但是TLE，在线等大佬，求剪枝