首页 > 代码库 > BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸

BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸

2024-08-10 21:58:09   219人阅读

传送门

很容易看出来这是一道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 }
View Code

 

BZOJ1933: [Shoi2007]Bookcase 书柜的尺寸


联系
我们