首页 > 代码库 > [Shoi2007]Bookcase 书柜的尺寸 dp
[Shoi2007]Bookcase 书柜的尺寸 dp
这道dp算是同类型dp中比较难的了,主要难点在于设置状态上;
如果像平时那样设置,必定爆空间没商量;
下面是一种思路:
先把输入进来的数据按h从大到小排序,这样就可以大大减少状态数,
然后设f[i][j][k]为前i本书第一个书柜厚度j,第二个书柜厚度k,第三个书柜厚度sum[i]-j-k的h最大值得最小和;
这样一是将h放在了里面,相当于一个方程思想,因为s可以由h,t算出来;
二是转移的时候,如果j,k或sum[i]-j-k为0,直接加上h,因为前面的h比后面的大,方便了转移;
但我最后也是心惊胆战的交了上去,幸运地A了;
这种题还是做的太少了,加油吧;
自己都不忍直视的代码->
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<ctime> 5 #include<cstring> 6 #include<string> 7 #include<algorithm> 8 #include<map> 9 #include<set>10 using namespace std;11 #define LL long long12 const long long inf=1000000000LL;13 int n,c=0;14 struct node{15 int h,t;16 bool operator<(const node& b)const{return h>b.h;}17 }e[72];18 LL f[2110][2110],sum[72];19 void init(){20 scanf("%d",&n);21 for(int i=1;i<=n;i++){scanf("%d%d",&e[i].h,&e[i].t);c+=e[i].t;}22 sort(e+1,e+n+1);23 for(int i=1;i<=n;i++)sum[i]=sum[i-1]+e[i].t;24 }25 void work(){26 memset(f,10,sizeof(f));27 f[0][0]=0;28 for(int i=1;i<=n;i++){29 for(int j=c/2+1;j>=0;j--)30 for(int k=c/2+1;k>=0;k--){31 if(sum[i]-j-k==e[i].t)f[j][k]+=e[i].h;32 if(j<e[i].t&&k<e[i].t)continue;33 if(j==e[i].t)f[j][k]=min(f[j][k],f[j-e[i].t][k]+e[i].h);34 if(j>e[i].t)f[j][k]=min(f[j][k],f[j-e[i].t][k]);35 if(k==e[i].t)f[j][k]=min(f[j][k],f[j][k-e[i].t]+e[i].h);36 if(k>e[i].t)f[j][k]=min(f[j][k],f[j][k-e[i].t]);37 }38 }39 long long ans=10000000000LL;40 for(int j=1;j<=c/2+1;j++)41 for(int k=1;k<=c/2+1;k++){42 if(c-j-k<=0)break;43 ans=min(ans,(f[j][k]>=inf?inf:f[j][k])*max(max(j,k),c-j-k));44 }45 cout<<ans<<endl;46 }47 int main(){48 init();49 work();50 return 0;51 }
[Shoi2007]Bookcase 书柜的尺寸 dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。