题解 P2160 【[SHOI2007]书柜的尺寸】

· · 题解

设 f_{i,j,k,l} 表示放了前 i 本书，第一层厚度为 j，第二层厚度为 k，第三层厚度为 l 的最小高度和

容易想到，我们将所有书按照高度从大到小排序，那么每一层的高度就是第一个放入该层的书的高度

记 sum_i=\sum\limits_{j=1}^i t_j显然，j+k+l=sum_i，则 l=sum_i-j-k，由此，我们可以省掉 l 这一维

再加一个滚动数组优化就可以啦

转移方程较为简单，见代码，采用刷表法比较好写

//timeuse:20min
const int N = 80,M = 2110;
int n;
struct book { int h,t; }a[N];
int f[2][M][M],sum[N];
void minn(int &a,int b) { if(a > b) a = b; }
int main()
{
    freopen("random.in","r",stdin);
    freopen("sol.out","w",stdout);
    n = read();for(int i = 1;i <= n;i++) a[i].h = read(),a[i].t = read();
    sort(a + 1,a + 1 + n,[&](book u,book v) { return u.h > v.h; });
    for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + a[i].t;
    memset(f[0],63,sizeof(f));f[0][0][0] = 0;
    for(int i = 1;i <= n;i++)
    {
        int now = i & 1,pre = now ^ 1;
        memset(f[now],63,sizeof(f[now]));
        for(int j = 0;j <= sum[i - 1];j++) for(int k = 0;k <= sum[i - 1];k++)
        {
            if(j == 0) minn(f[now][j + a[i].t][k],f[pre][j][k] + a[i].h);
            else minn(f[now][j + a[i].t][k],f[pre][j][k]);
            if(k == 0) minn(f[now][j][k + a[i].t],f[pre][j][k] + a[i].h);
            else minn(f[now][j][k + a[i].t],f[pre][j][k]);
            if(sum[i - 1] - j - k == 0) minn(f[now][j][k],f[pre][j][k] + a[i].h);
            else minn(f[now][j][k],f[pre][j][k]);
        }
    }ll ans = LINF;
    for(int i = 1;i <= sum[n];i++) for(int j = 1;j <= sum[n];j++) if(sum[n] - i - j > 0)
        ans = min(ans,(ll)max(max(i,j),sum[n] - i - j) * f[n & 1][i][j]);
    fprint(ans);
    return 0;
}