bzoj 1933: [Shoi2007]Bookcase 书柜的尺寸

.

题意：给出n本书的高度和厚度，把它们放在三行的书架上（每一行至少一本书），问书架正面的最小面积。
题解：先按高度从大到小排序，保证后面加入的书不会对高度造成影响，再dp。$f[i][j][k]$表示前i本书第一行的宽度为j，第三行的宽度为k的最小高度。

$f[i][j+a[i].t][k]=min(f[i][j+a[i].t][k],f[i-1][j][k]+(j==0)\times a[i].h)\\\ f[i][j][k+a[i].t]=min(f[i][j][k+a[i].t],f[i-1][j][k]+(k==0)\times a[i].h)\\\ f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(j+k==sum[i-1])\times a[i].h)$

sum[i]表示前i本书的厚度和。第一维滚一下就好了。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,f[2][2200][2200],sum[80],ans=2147483647;
struct hh
{
    int h,t;
}a[80];

int cmp(hh x,hh y)
{
    return x.h>y.h;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].h,&a[i].t);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    sum[i]=sum[i-1]+a[i].t;
    int p=0,q=1;
    for(int i=1;i<=n;i++)
    {
        p^=1;
        q^=1;
        memset(f[p],63,sizeof(f[p]));
        for(int j=0;j<=sum[i-1];j++)
        {
            for(int k=0;j+k<=sum[i-1];k++)
            {
                f[p][j+a[i].t][k]=min(f[p][j+a[i].t][k],f[q][j][k]+(j==0)*a[i].h);
                f[p][j][k+a[i].t]=min(f[p][j][k+a[i].t],f[q][j][k]+(k==0)*a[i].h);
                f[p][j][k]=min(f[p][j][k],f[q][j][k]+(j+k==sum[i-1])*a[i].h);
            }
        }
    }
    for(int i=1;i<sum[n];i++)
    {
        for(int j=1;i+j<sum[n];j++)
        if(f[p][i][j]<=1000)
        ans=min(ans,f[p][i][j]*max(i,max(j,sum[n]-i-j)));
    }
    printf("%d",ans);
}