laekov

老早之前就听说过的题。好像讲过不只一遍。不过才从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);

}