首页 > 代码库 > 基础dp C Monkey and Banana （类最长上升子序列）
基础dp C Monkey and Banana （类最长上升子序列）
题目大意：有一个猴儿和一些种类的箱子，每种类箱子有各自的长宽高，数目有无限个。猴子想把箱子尽可能的堆积起来，
堆积的条件通俗的讲就是放在下面的箱子能够撑得住上面的箱子，按数学建模来说就是放在下面的箱子的长和宽要比放在上
面的要大（严格大于）；由于每种箱子虽然数量是无限的，但是肯定不能同种箱子直接累积，因为那样底面的边长就相等了，
这样就是不合法的了，所以每种箱子可以转换成六种情况的不同箱子（分别作为长宽高），之后就是个最长满足条件的高度序
列就行了，即套用最长上升子序列算法思想即可。
#include <stdio.h> #include <algorithm> #include <string.h> using namespace std; #define oo 0x3f3f3f3f struct ad { int x, y, z; bool operator < (const ad t)const { return x > t.x; } } blocks[220]; int cnt, dp[220]; void Add(int x, int y, int z) { blocks[cnt].x = x; blocks[cnt].y = y; blocks[cnt].z = z; cnt++; } int main() { int n, icase = 1; while(scanf("%d", &n), n) { cnt = 0; for(int i=1; i<=n; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c);///同种箱子可以使用无限个，但是底边严格缩小，那么可以 Add(a, b, c); ///抽象成六种底边和高度的箱子(六种放法) Add(a, c, b); Add(b, a, c); Add(b, c, a); Add(c, a, b); Add(c, b, a); } sort(blocks, blocks+cnt); memset(dp, 0, sizeof(dp)); int ans = 0; for(int i=0; i<cnt; i++)///类最长上升子序列（最长严格底边下降序列） { dp[i] = blocks[i].z;///单独放最下面的情况 for(int j=0; j<i; j++) { if(blocks[j].x > blocks[i].x && blocks[j].y > blocks[i].y) dp[i] = max(dp[i], dp[j]+blocks[i].z); } ans = max(ans, dp[i]); } printf("Case %d: maximum height = %d\n", icase++, ans); } return 0; }
基础dp C Monkey and Banana （类最长上升子序列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。