题解

思路分析

这是一道 DP + 枚举优化 的三维优化问题。

问题建模

• $n$ 本书分成3层（每层至少1本）
• 每层的高度 = 该层书的最大高度
• 每层的厚度 = 该层书的厚度之和
• 目标：最小化 $(\sum \text{高度}) \times (\max \text{厚度})$

核心思路

1. 排序优化

将书按高度降序排序：

• 每层的最大高度就是该层第一本书的高度
• 避免枚举时重复计算高度

2. DP 状态定义

定义 $f[i][j][k]$ 表示：

• 前 $i$ 本书已分配
• 第一层厚度和为 $j$
• 第二层厚度和为 $k$
• 三层高度之和的最小值

状态转移：

• 将第 $i+1$ 本书放入第一层：$$f[i+1][j+t_{i+1}][k] = \min(f[i][j][k] + h_{i+1} \cdot [j = 0]) $$
• 放入第二层或第三层类似

3. 滚动数组优化

由于只需要前一层的状态，使用滚动数组优化空间。

4. 答案计算

枚举所有可能的 $(j, k)$，计算：

$$\text{ans} = \min(f[n][j][k] \times \max(j, k, sum[n] - j - k)) $$

算法步骤

1. 预处理：

   • 按高度降序排序
   • 计算厚度前缀和

2. DP 转移：

   • 枚举书本
   • 枚举两层厚度
   • 枚举放入哪一层
   • 更新状态

3. 计算答案：

   • 枚举所有有效的 $(j, k)$
   • 计算表面积
   • 取最小值

4. 输出结果

复杂度分析

• 排序：$O(n \log n)$
• DP：$O(n \cdot S^2)$，$S = \sum t_i \leq 2100$
• 总时间复杂度：$O(n \cdot S^2)$
• 空间复杂度：$O(S^2)$

#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;
}

题解

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