由于书柜的深度是固定的（显然，它应该等于那本最宽的书的长度），所以要求书柜的体积最小就是要求S最小。Tom离答案只有一步之遥了。不过很遗憾，Tom并不擅长于编程，于是他邀请你来帮助他解决这个问题。Day2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~DP+思路~
求最大高、之和，和最大、宽之和的乘积的最小值~（注意断句！）
首先，我们可以用f[i][j][k][z]表示目前DP到第i本书，三个柜的书的宽度分别为j,k,z的最小的最大高的值，但是显然像这样所有维度都记录的话会MLE，所以我们只能记录一部分的状态。
注意到DP到i时，已有的书的宽度之和是一定的，所以我们只需要记录三块中的两块的宽度之和就可以了。而i对递推过程无影响，所以把i维换成滚动形式。
所以用f[kkz][j][k]表示目前用kkz^1更新kkz，三个书柜宽度分别为j,k,sum[i-1]-j-k的最小的最大高度，然后预处理出宽度的前缀和sum[i]，直接DP即可~
#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;}
新闻热点
疑难解答
