首页 > 代码库 > BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸
BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸
传送门
很容易看出来这是一道DP题,那么怎么设置状态就成了这道题的关键。本题有点特殊的地方是有两个维度的状态,而每个维度又有三个部分的参数,如果全部设置出来的话肯定会MLE。首先对书的厚度状态简化。
书的厚度是求和的,这个显然不能作为状态的值,作为状态的参数是比较好的, 30*70=2100 2100^3是内存无法接受的,简化状态求出前i本书的前缀和sum[i],如果第一层的厚度是i,第二层的厚度是j,那么第三层的状态显然是sum[i]-j-k,bingo,内存的问题解决了。显然两个维度一个维度表状态另一个维度显然表示权值。但是问题是,书是三层的高度,不可能把每一层都暴力表示出来,所以巧妙的地方是把书的高度递减排序。然后这个问题就显然很好解决了。
1 //BZOJ 1933 2 //by Cydiater 3 //2016.8.26 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <queue> 9 #include <map>10 #include <ctime>11 #include <iomanip>12 #include <cmath>13 #include <cstdlib>14 #include <cstdio>15 using namespace std;16 #define ll int17 #define up(i,j,n) for(ll i=j;i<=n;i++)18 #define down(i,j,n) for(ll i=j;i>=n;i--)19 const int MAXN=2505;20 const int oo=0x3f3f3f3f;21 inline int read(){22 char ch=getchar();int x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll N,f[2][2105][2105],sta=0,lim=0,sum[75],ans=oo;28 struct _data{29 ll h,t;30 }a[75];31 namespace solution{32 inline bool cmp(_data x,_data y){return x.h>y.h;}33 void init(){34 N=read();35 memset(sum,0,sizeof(sum));36 up(i,1,N){37 a[i].h=read();a[i].t=read();38 lim+=a[i].t;39 }40 sort(a+1,a+N+1,cmp);41 up(i,1,N)sum[i]=sum[i-1]+a[i].t;42 }43 void dp(){44 memset(f,10,sizeof(f));45 f[sta][0][0]=0;46 up(i,1,N){47 sta^=1;memset(f[sta],10,sizeof(f[sta]));48 ll h=a[i].h,t=a[i].t;49 down(j,sum[i-1],0)down(k,sum[i-1],0){50 if(j+k>sum[i-1])continue;51 if(f[sta^1][j][k]>1000000)continue;52 if(j==0) f[sta][t][k]=min(f[sta][t][k],f[sta^1][j][k]+h);53 else f[sta][j+t][k]=min(f[sta][j+t][k],f[sta^1][j][k]);54 if(k==0) f[sta][j][t]=min(f[sta][j][t],f[sta^1][j][k]+h);55 else f[sta][j][k+t]=min(f[sta][j][k+t],f[sta^1][j][k]);56 if(sum[i-1]-j-k==0) f[sta][j][k]=min(f[sta][j][k],f[sta^1][j][k]+h);57 else f[sta][j][k]=min(f[sta][j][k],f[sta^1][j][k]);58 }59 }60 }61 void output(){62 up(i,1,lim)up(j,1,lim)if(sum[N]-i-j>0&&f[sta][i][j]<10000){63 ans=min(ans,max(max(i,j),sum[N]-i-j)*f[sta][i][j]);64 }65 cout<<ans<<endl;66 }67 }68 int main(){69 //freopen("input.in","r",stdin);70 using namespace solution;71 init();72 dp();73 output();74 return 0;75 }
BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。