http://acm.hdu.edu.cn/showproblem.php?pid=1069 一道经典的DP题目，类似于求最长递增子序列吧。 题意： 一堆科学家研究猩猩的智商，给他n个长方体， 然后，将一个香蕉挂在屋顶，让猩猩通过 叠长方体来够到香蕉。 现在给你n个长方体，计算，最高能堆多高。 要求位于上面的长方体的长要大于（注意不是大于等于）下面长方体的长，上面长方体的宽大于下面长方体的宽。 解题： 一个长方体，可以有6种不同的摆法。 例如： 第一个例子： 10 20 30 它有6中摆法： 长  宽    高 10  20  30 20  30  10 30  10  20 10  30  20 20  10  30 30  20  10 然后我们把它排序 排序之后应该是这样的 10 20 30 10 30 10 20 10 30 20 30 10 30 10 20 30 20 10 因为数据中 长方体种类最多30种，也就是说数组最大可以开到 30*6=180 完全可以 然后用dp[i]来存，到第i个木块，最高可以累多高。 当然，长方体先要以长度排序，长度相同则宽度小的在上。 这道题有点难理解 代码： #include #include using namespace std; struct Cuboid //类 { int l,w,h; } cd[181]; int dp[181]; bool cmp( Cuboid cod1,Cuboid cod2 ) { if( cod1.l==cod2.l ) return cod1.w>n && n ) { len=0; // 每组数都可以变换为6种长方体 for(i=0;i>z1>>z2>>z3; //输入3个数，不知道哪个是长宽高， cd[len].l=z1,cd[len].w=z2,cd[len++].h=z3;//l是长，w是宽，h是高 cd[len].l=z1,cd[len].w=z3,cd[len++].h=z2; cd[len].l=z2,cd[len].w=z1,cd[len++].h=z3; cd[len].l=z2,cd[len].w=z3,cd[len++].h=z1; cd[len].l=z3,cd[len].w=z1,cd[len++].h=z2; cd[len].l=z3,cd[len].w=z2,cd[len++].h=z1; } sort(cd,cd+len,cmp); dp[0]=cd[0].h;// 构建dp数组 int max_h; for(i=1;idp[j]?max_h:dp[j]; //比较大小 } dp[i]=cd[i].h+max_h; //高度 } // 再次搜索 所有dp中最大值 max_h=0; for(i=0;i