C++11(clang++ 3.9) 解法, 执行用时: 425ms, 内存消耗: 35056K, 提交时间: 2020-04-01 19:13:55

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,f[2][2101][2101],inf,kkz,sum[71],h,w,ans;
struct node
{
	int h,w;
}a[71];
bool operator <(node u,node v)
{
	return u.h>v.h;
}
int read()
{
	int totnum=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		totnum=(totnum<<1)+(totnum<<3)+ch-'0';
		ch=getchar();
	}
	return totnum*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	a[i].h=read(),a[i].w=read();
	memset(f[kkz],127/3,sizeof(f[kkz]));
	ans=inf=f[kkz][0][0];
	f[kkz][0][0]=0;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	sum[i]=sum[i-1]+a[i].w;
	for(int i=1;i<=n;i++)
	{
		kkz^=1;
		h=a[i].h;
		w=a[i].w;
		memset(f[kkz],127/3,sizeof(f[kkz]));
		for(int j=sum[i-1];~j;j--)
		for(int k=sum[i-1];~k;k--)
		if(j+k<=sum[i-1]&&f[kkz^1][j][k]<inf)
		{
			if(j) f[kkz][j+w][k]=min(f[kkz][j+w][k],f[kkz^1][j][k]);
			else f[kkz][w][k]=min(f[kkz][j][k],f[kkz^1][j][k]+h);
			if(k) f[kkz][j][k+w]=min(f[kkz][j][k+w],f[kkz^1][j][k]);
			else f[kkz][j][w]=min(f[kkz][j][w],f[kkz^1][j][k]+h);
			if(j+k<sum[i-1]) f[kkz][j][k]=min(f[kkz][j][k],f[kkz^1][j][k]);
			else f[kkz][j][k]=min(f[kkz][j][k],f[kkz^1][j][k]+h);
		}
	}
	for(int i=1;i<sum[n];i++)
	for(int j=1;j<sum[n];j++)
	if(i+j<sum[n]&&f[kkz][i][j]<inf)
	ans=min(ans,max(max(i,j),sum[n]-i-j)*f[kkz][i][j]);
	printf("%d\n",ans);
	return 0;
}