老早之前就听说过的题。好像讲过不只一遍。不过才从bzoj上翻出来。
记得是神奇的dp优化。为啥这年头卡常数的题这么多。
首先肯定这玩意多项式可解。六维状态肯定能搞定。然后会mle+tle。
首先考虑从高到低放书，那么后面的如果不新开一行的话对高度没有影响。瞬间少了3维状态。
然后发现只要知道两维的总宽度和当前是第几位，就能知道第三维的宽度。于是一维2100缩70，开滚动可过。
当然还是需要一些常数优化的技艺。比如用宽度直接判断这一行有没有书。这样可以省下不少时间，而且好像只能这样才存得下。64MB太紧了点。另外把函数里的int改成const int&会变慢，不知为何。
居然花了这么久才搞出来。我太年轻了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct book {
int w, h;
};
inline bool cmpBook(const book& a, const book& b) {
return a. h > b. h;
}
const int maxn = 71;
const int maxw = 2109;
const int inf = 0x3f3f3f3f;
int n, f[2][maxw][maxw], sw;
book a[maxn];
inline void upmin(int& _a_, int _b_) {
if (_a_ > _b_)
_a_ = _b_;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
sw = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d%d", &a[i]. h, &a[i]. w);
sw += a[i]. w;
}
sort(a, a + n, cmpBook);
memset(f, 0x3f, sizeof(f));
int cur = 0, prv = 1;
f[cur][0][0] = a[0]. h;
for (int i = 1; i < n; ++ i) {
swap(cur, prv);
for (int j = 0; j <= sw; ++ j)
for (int k = 0; k <= sw; ++ k)
f[cur][j][k] = inf;
for (int j = 0; j <= sw; ++ j)
for (int k = 0; k <= sw; ++ k)
if (f[prv][j][k] < inf) {
upmin(f[cur][j][k], f[prv][j][k]);
if (k) {
upmin(f[cur][j][k + a[i]. w], f[prv][j][k]);
if (j)
upmin(f[cur][j + a[i]. w][k], f[prv][j][k]);
else
upmin(f[cur][j + a[i]. w][k], f[prv][j][k] + a[i]. h);
}
else
upmin(f[cur][j][k + a[i]. w], f[prv][j][k] + a[i]. h);
}
}
int ans = inf;
for (int j = 1; j <= sw; ++ j)
for (int k = 1; k <= sw; ++ k)
if (sw - j - k && f[cur][j][k] < inf)
upmin(ans, f[cur][j][k] * max(max(j, k), sw - j - k));
printf("%d\n", ans);
}