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
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue> using namespace std;
const int maxn=;
int n;
int d[];
struct node
{
int l,w,h;
bool operator > (const node& p)const
{
return (l>p.l)&&(w>p.w);
}
node(int ll,int ww,int hh):l(ll),w(ww),h(hh){}
node(){}
}; bool cmp(const node& x,const node& y)
{
return x.l*x.w<y.l*y.w;
}
int dp[*maxn];
vector<node> ln;
int main()
{
int kas=;
while(scanf("%d",&n)==&&n)
{
memset(dp,,sizeof(dp));
ln.clear();
for(int i=;i<n;i++)
{
scanf("%d%d%d",&d[],&d[],&d[]);
sort(d,d+);
ln.push_back(node(d[],d[],d[]));
ln.push_back(node(d[],d[],d[]));
ln.push_back(node(d[],d[],d[]));
}
// sort(ln,ln+n);
sort(ln.begin(),ln.end(),cmp);
//dp[i]表示以ln[i]这块砖为最大砖的 最大高度 dp[]=ln[].h;
int ans=dp[];
for(int i=;i<ln.size();i++)
{
dp[i]=ln[i].h;
for(int k=i-;k>=;k--)
{
// if(ln[k]<ln[i])
if(ln[i]>ln[k])
{
dp[i]=max(dp[i],dp[k]+ln[i].h);
}
}
ans=max(ans,dp[i]);
}
printf("Case %d: maximum height = %d\n",kas++,ans); }
return ;
}
【疑问】其实还是不太明白贪心那里.....模糊不清....为什么是这样排序？先按面积，然后再判断是不是严格小