题意是给出 n 个矩形的长宽高 (每个矩形个数无限), 问用这些矩形搭塔最高可以搭多高. 要求下面一层矩形的长和宽必须大于上面一层矩形的长和宽.(每一个非正方体都有 6 种放置方法).
相当于求最大递减的子序列的和. 每输入一个立方体, 就将这个立方体的 6 种放置方式保存. 然后从小到大的排序. i 从 1 开始循环到最后一个, 每次找从 0 到 i-1 内符合条件的最高立方体, dp[i] 就储存当前层数的最高高度.
参考文章: https://blog.csdn.net/lttree/article/details/26606947
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- struct cube{
- int l,w,h;
- cube() {}
cube(int _l,int _w,int _h):l(_l),w(_w),h(_h) {}
- }cd[181];
- bool cmp(cube a,cube b){
- if(a.l==b.l) return a.w<b.w;
- else return a.l<b.l;
- }
- int dp[181];
- int main(){
- int n,num=1,l,w,h;
- while(~scanf("%d",&n)&&n){
- int len=0;
- for(int i=0;i<n;i++){
- scanf("%d %d %d",&l,&w,&h);
- cd[len++]=cube(l,w,h);
- cd[len++]=cube(l,h,w);
- cd[len++]=cube(h,l,w);
- cd[len++]=cube(h,w,l);
- cd[len++]=cube(w,l,h);
- cd[len++]=cube(w,h,l);
- }
- sort(cd,cd+len,cmp);
- dp[0]=cd[0].h;
- int max_h;
- for(int i=1;i<len;i++){
- max_h=0;
- for(int k=0;k<i;k++){
- if(cd[k].l<cd[i].l&&cd[k].w<cd[i].w)
- max_h=max_h>dp[k]?max_h:dp[k];
- }
- dp[i]=max_h+cd[i].h;
- }
- max_h=0;
- for(int i=0;i<len;i++){
- if(max_h<dp[i])
- max_h=dp[i];
- }
- printf("Case %d: maximum height = %d\n",num++,max_h);
- }
- return 0;
- }
- hdu 1069
来源: http://www.bubuko.com/infodetail-2578516.html