hdu 1069 Monkey and Banana(dp 最长上升子序列)

本文主要是介绍hdu 1069 Monkey and Banana(dp 最长上升子序列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1069

题意：有n种类型的木块，木块是长方体，已知每种长方体的长宽高，且每种木块的数量是无限的。问这些木块能够摞起来的最高高度，摞起来的规则是上面的木块的长和宽必须严格小于下面木块的长和宽。

思路：把每种木块分成六种木块，然后对x排序，再对x和y求类似于最长上升子序列。这里dp对应的不是个数，而是摞起来的最高高度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;struct node
{int x,y,z;bool operator < (const struct node &tmp)const{if(x == tmp.x)return y < tmp.y;return x < tmp.x;}
}rec[200];int cnt;
int dp[200];
void init(int x, int y, int z)
{rec[++cnt] = (struct node){x,y,z};rec[++cnt] = (struct node){x,z,y};rec[++cnt] = (struct node){y,x,z};rec[++cnt] = (struct node){y,z,x};rec[++cnt] = (struct node){z,x,y};rec[++cnt] = (struct node){z,y,x};
}int main()
{int n,x,y,z;int item = 1;while(~scanf("%d",&n) &&n){cnt = 0;for(int i = 1; i <= n; i++){scanf("%d %d %d",&x,&y,&z);init(x,y,z);}sort(rec+1,rec+1+cnt);int ans = -1;for(int i = 1; i <= cnt; i++){dp[i] = rec[i].z;for(int j = 1; j < i; j++){if(rec[i].x > rec[j].x && rec[i].y > rec[j].y && dp[i] < (dp[j]+rec[i].z))dp[i] = dp[j]+rec[i].z;}}for(int i = 1; i <= cnt; i++){if(ans < dp[i])ans = dp[i];}printf("Case %d: maximum height = ",item++);printf("%d\n",ans);}return 0;
}

这篇关于hdu 1069 Monkey and Banana(dp 最长上升子序列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---