https://vjudge.net/contest/68966#problem/C
【参考】http://blog.csdn.net/qinmusiyan/article/details/7986263
【题意】：多组测试数据
每组测试数据给出n个砖块的长、宽、高，每种砖块有无穷多个，可以有三种不同的放置方法（xy;xz;yz），下面的砖要比上面的砖的长和宽都大，问最大的高度是多少。
【思路】：【贪心+dp】每块砖有三种放置方法，把所有砖的所有状态都压入vector,先贪心，按面积大小排序，使它本身尽可能的满足单调递增;dp[i]表示以ln[i]这块砖为最大砖的最大高度，则dp[i]=max(dp[k]+ln[i].h,ln[i].h);其中0<=k<=i-1且ln[i]>ln[k],一定要注意自己重载的运算符为>,不能写成ln[k]<ln[i]....orz
【代码】
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 9 using namespace std; 10 const int maxn=35; 11 int n; 12 int d[3]; 13 struct node 14 { 15 int l,w,h; 16 bool operator > (const node& p)const 17 { 18 return (l>p.l)&&(w>p.w); 19 } 20 node(int ll,int ww,int hh):l(ll),w(ww),h(hh){} 21 node(){} 22 }; 23 24 bool cmp(const node& x,const node& y) 25 { 26 return x.l*x.w<y.l*y.w; 27 } 28 int dp[3*maxn]; 29 vector<node> ln; 30 int main() 31 { 32 int kas=1; 33 while(scanf("%d",&n)==1&&n) 34 { 35 memset(dp,0,sizeof(dp)); 36 ln.clear(); 37 for(int i=0;i<n;i++) 38 { 39 scanf("%d%d%d",&d[0],&d[1],&d[2]); 40 sort(d,d+3); 41 ln.push_back(node(d[2],d[1],d[0])); 42 ln.push_back(node(d[2],d[0],d[1])); 43 ln.push_back(node(d[1],d[0],d[2])); 44 } 45 // sort(ln,ln+n); 46 sort(ln.begin(),ln.end(),cmp); 47 //dp[i]表示以ln[i]这块砖为最大砖的 最大高度 48 49 dp[0]=ln[0].h; 50 int ans=dp[0]; 51 for(int i=1;i<ln.size();i++) 52 { 53 dp[i]=ln[i].h; 54 for(int k=i-1;k>=0;k--) 55 { 56 // if(ln[k]<ln[i]) 57 if(ln[i]>ln[k]) 58 { 59 dp[i]=max(dp[i],dp[k]+ln[i].h); 60 } 61 } 62 ans=max(ans,dp[i]); 63 } 64 printf("Case %d: maximum height = %d ",kas++,ans); 65 66 67 } 68 return 0; 69 }
【疑问】其实还是不太明白贪心那里.....模糊不清....为什么是这样排序？先按面积，然后再判断是不是严格小