[SHOI2007]书柜的尺寸

题意

有一些书放到三层书架上，满足每层至少一本，最小化

[S=left(sum_{j=1}^3 max_{i in S_j} h_i ight) imes left(max_{j=1}^3 sum_{i in S_j} t_i ight) ]

其中(n leq 70,h_i leq 300,t_i leq 30)

思路

这数据范围谁会想到这么暴力啊

显然动态规划，由于高度最值放下标不会做，所以将宽度和放在下标

设(f_{i,j,k})表示选了前(i)本书，第一层宽度(j)，第二层宽度(k)时的最小高度，即最小化(f_{n,j,k}*max(j,k,n-j-k)) (,) ((j,k geq 1) 且 (j+k < n))，注意每一层必须要有书

由于没有记录高度最值，所以不能转移；将高度从大到小排序即可，一层加入的第一本书一定是最高的

时间上可能过不了（不然为什么开(5s)的时限），将每次(DP)的(sum)宽度设为前(i)本书的宽度和即可将(n*2100^2)的复杂度优化至玄学

Code

#include<bits/stdc++.h>
#define N 2101
#define re register
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n,sum;
int f[2][N][N];
struct Node { int h,t; }nd[N];

template <class T>
void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
bool cmp(Node a,Node b) { return a.h>b.h; }

int main()
{
	read(n);
	for(int i=1;i<=n;++i) read(nd[i].h),read(nd[i].t);
	sort(nd+1,nd+n+1,cmp);
	int now=1,las=0;
	for(re int i=1;i<=n;++i)
	{
		swap(now,las);
		sum+=nd[i].t;
		for(re int j=0;j<=sum;++j)
		{
			for(re int k=0;k+j<=sum;++k)
			{
				f[now][j][k]=2000000000;
				int td=sum-j-k;
				//放第一层
				if(j>=nd[i].t) f[now][j][k] = Min(f[now][j][k],f[las][j-nd[i].t][k] + (j==nd[i].t)*nd[i].h);
				//第二层 
				if(k>=nd[i].t) f[now][j][k] = Min(f[now][j][k],f[las][j][k-nd[i].t] + (k==nd[i].t)*nd[i].h);
				//第三层 
				if(td>=nd[i].t) f[now][j][k] = Min(f[now][j][k],f[las][j][k] + (td==nd[i].t)*nd[i].h);
			}
		}
	}
	int ans=2000000000;
	for(int i=1;i<sum;++i)
	  for(int j=1;i+j<sum;++j)
		ans=Min(ans,(long long)Max(Max(i,j),sum-i-j)*f[now][i][j]);
	cout<<ans<<endl;
	return 0;
}