题解

首先按照书的高度从高到低排序。如此一来，每一层书架的最大高度恰好是该层第一次放入的书的高度，之后无论再放哪些书都不会改变这一层的高度。我们用两本书的厚度和就能推出第三层的厚度，因此把问题转化为二维状态 DP。

设 sum[i] 为前 i 本书厚度之和。定义状态 dp[i][a][b] 表示已经处理了前 i 本书，第一、第二层的总厚度分别为 a 和 b 时，三层高度之和的最小值（第三层的厚度为 sum[i] - a - b，高度同样由第一次放置书时确定）。转移时我们有三种选择，把第 i+1 本书放在三层中的任意一层，如果该层此前为空，则把这层的高度记为当前书的高度，否则高度保持不变。由于厚度总和不会超过 2100，且书本数量不超过 70，状态规模可以接受，代码中用滚动数组节省内存。

DP 完成后还需要枚举三层的厚度组合。对于第一层厚度 a、第二层厚度 b，第三层厚度自然为 sum[n] - a - b。三层必须全部非空，体积的横截面积即为“三层高度之和 × 三层最大厚度”。因此我们遍历所有 a、b，过滤掉其中某一层为空的情况，取 max(a, b, sum[n]-a-b) × dp[n][a][b] 的最小值就是答案。

#include<bits/stdc++.h>
using namespace std;
int f[2][2110][2110],n,sum[110];
typedef long long ll;
ll res=0x3f3f3f3f3f3f3f3f;
pair<int,int>p[100];
bool cmp(pair<int,int>x,pair<int,int>y){
    return x.first>y.first;
}
int main(){
    scanf("%d",&n);
	memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+p[i].second;
    f[0][0][0]=0;
    for(int i=0;i<n;i++){
        memset(f[!(i&1)],0x3f3f3f3f,sizeof(f[!(i&1)]));
        for(int j=0;j<=sum[i];j++){
        	for(int k=0;j+k<=sum[i];k++){
            	f[!(i&1)][j+p[i+1].second][k]=min(f[!(i&1)][j+p[i+1].second][k],f[i&1][j][k]+p[i+1].first*(!j));
            	f[!(i&1)][j][k+p[i+1].second]=min(f[!(i&1)][j][k+p[i+1].second],f[i&1][j][k]+p[i+1].first*(!k));
            	f[!(i&1)][j][k]=min(f[!(i&1)][j][k],f[i&1][j][k]+p[i+1].first*(!(sum[i]-j-k)));
        	}
		}
    }
    for(int i=1;i<sum[n];i++){
    	for(int j=1;i+j<sum[n];j++){
    		res=min(res,1ll*max(max(i,j),sum[n]-i-j)*f[n&1][i][j]);
		}
	}
    printf("%d\n",res);
    return 0;
}