
/* 这道题需要表示的状态特别多,所以不能直接写。
一个很巧妙的方法是将高度从大到小排序,那么每个集合的第一个元素的h就是最大h。
即使这样2100^3的复杂度也是不够的,我们可以考虑省去第三维(可以用总的减去前两维),然后转移时f表示最大高度之和就行了。 */ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define N 80 #define M 2500 #define inf 1000000000 using namespace std; int f[2][M][M],n,m,sum[N]; struct node{ int h,t; };node a[N]; bool cmp(const node&s1,const node&s2){ return s1.h>s2.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+n+1,cmp); for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i].t; m+=a[i].t; } memset(f,10,sizeof(f)); int sta=0;f[0][0][0]=0; for(int i=1;i<=n;i++){ sta^=1;memset(f[sta],10,sizeof(f[sta])); for(int j=sum[i-1];j>=0;j--) for(int k=sum[i-1];k>=0;k--){ int h=a[i].h,t=a[i].t; if(j+k>sum[i-1])continue; if(f[sta^1][j][k]>1000000)continue; if(!j) f[sta][t][k]=min(f[sta][t][k],f[sta^1][j][k]+h); else f[sta][j+t][k]=min(f[sta][j+t][k],f[sta^1][j][k]); if(!k) f[sta][j][t]=min(f[sta][j][t],f[sta^1][j][k]+h); else f[sta][j][k+t]=min(f[sta][j][k+t],f[sta^1][j][k]); if(sum[i-1]==j+k) f[sta][j][k]=min(f[sta][j][k],f[sta^1][j][k]+h); else f[sta][j][k]=min(f[sta][j][k],f[sta^1][j][k]); } } int ans=inf; for(int j=1;j<=m;j++) for(int k=1;j+k<m;k++){ if(f[n&1][j][k]>100000)continue; ans=min(ans,max(max(j,k),m-j-k)*f[n&1][j][k]); } printf("%d",ans); return 0; }
原文:http://www.cnblogs.com/harden/p/6254878.html