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

題目大意：給出n種長方體的x，y，z（任意個），然后堆起來（要求嚴(yán)格小于自己下面的長方體），求能達(dá)到的最大高度。

經(jīng)典的矩形嵌套：把每種長方體的6種方法都存儲起來，然后排序，然后再像上升子序列dp一樣。見注釋

AC代碼：

#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <stdlib.h> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> #include <sstream> #include <stack> using namespace std; #define mem(a,b) memset((a),(b),sizeof(a)) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define forn(i, x, n) for(int i = (x); i < n; i++) #define nfor(i, x, n) for(int i = n-1; i >= x; i--) typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-5; const ll mod = 1e9+7;struct node{int l, w, h; }stu[200]; int dp[200];//dp[i] 表示 i能達(dá)到的最高高度 bool cmp(node a, node b) {//先x 后 y if(a.l == b.l)return a.w < b.w;return a.l < b.l; }int main() {int n, x, y, z, cur;int icase = 1;while(~scanf("%d", &n),n) {cur = 0;while(n--) {scanf("%d%d%d", &x, &y, &z);//存儲6種狀態(tài) stu[cur].l = x; stu[cur].w = y; stu[cur++].h = z; stu[cur].l = x; stu[cur].w = z; stu[cur++].h = y;stu[cur].l = y; stu[cur].w = z; stu[cur++].h = x;stu[cur].l = y; stu[cur].w = x; stu[cur++].h = z;stu[cur].l = z; stu[cur].w = x; stu[cur++].h = y;stu[cur].l = z; stu[cur].w = y; stu[cur++].h = x;}sort(stu, stu+cur, cmp);//排序 mem(dp, 0);int maxx = -inf;forn(i, 0, cur) {dp[i] = stu[i].h;//初始化 forn(j, 0, i) {//找到使自己最高的 if(stu[j].l < stu[i].l && stu[j].w < stu[i].w) {dp[i] = max(dp[j] + stu[i].h, dp[i]);}}maxx = max(maxx, dp[i]);//更新最高高度 }maxx = max(0, maxx);printf("Case %d: maximum height = %d\n", icase++, maxx);} }

?

總結(jié)

以上是生活随笔為你收集整理的kuangbin专题十二 HDU1069 Monkey and Banana的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。