【HDU 1069 Monkey and Banana】 排序+DP

HDU1069
题意就是一个小猴子有n种不同的长方体，每种有无数个，小猴子想把长方体垒到最高，要求上面的长方体的下表面严格小于下面的长方体的上表面，
根据题意我们知道一个长方体最多有六种可利用状态，我们按照长度为第一关键字，宽度为第二关键字排序，这样就保证了合法的拜访状态一定是按照这个顺序进行的，我们就可以n^2枚举转移了。
这一类DP有一个特点，先排序保证最优状态一定是按照这个顺序进行的，再在这个排序之后的序列上DP。
DP转移方程为：
$dp[i]=max(dp[i],dp[j]+v[i].c) --$$v[i].a>v[j].a$&$v[i].b>v[j].b$
HDU1069代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define dbg(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
const int maxn = 1e3+5;
int dp[maxn];
struct data
{int a,b,c;
}v[maxn];
bool cmp(const data &a,const data &b)
{if(a.a==b.a){if(a.b==b.b){return a.c<b.c;}else{return a.b<b.b;}}else{return a.a<b.a;}
}
int main()
{int n;int T=1;while(scanf("%d",&n)!=EOF){if(n==0) break;int cnt=0;for(int i=1;i<=n*6;i++) dp[i]=0;for(int i=1;i<=n;i++){int a[3];scanf("%d%d%d",&a[0],&a[1],&a[2]);sort(a,a+3);do{v[++cnt].a=a[0];v[cnt].b=a[1];v[cnt].c=a[2];}while (next_permutation(a,a+3));}v[0].a=0;v[0].b=0;v[0].c=0;sort(v+1,v+1+cnt,cmp);for(int i=1;i<=cnt;i++){for(int j=i-1;j>=0;j--){if(v[i].a>v[j].a&&v[i].b>v[j].b){dp[i]=max(dp[i],dp[j]+v[i].c);}}}int ans=0;for(int i=1;i<=cnt;i++) ans=max(ans,dp[i]);printf("Case %d: maximum height = %d\n",T++,ans);}return 0;
}