題意：給定n個長方體，然后堆積最高的塔，要求上面的面積小于下面的面積。

思路：Dp，先把長方體的所有放的情況都構造出來放到數組里，對于當前節點，如果能夠在前面找到面積比當前小，高度累加比當前高的則轉移狀態。

code：

#include <bits/stdc++.h> using namespace std;#define ft(i,s,t) for(int i=s;i<=t;i++)const int N=95; struct node {int x,y,h; }g[N]; int dp[N],v[3];bool cmp(node a,node b){if (a.x==b.x) return a.y<b.y;return a.x<b.x; } int main() {int n,ca=1;while(~scanf("%d",&n),n){int l=0;ft(j,0,n-1){ft(i,0,2) scanf("%d",&v[i]);sort(v,v+3);ft(i,0,2){g[l+i].h=v[(0+i)%3];g[l+i].x=v[(2+i)%3];g[l+i].y=v[(1+i)%3];}swap(g[l+1].x,g[l+1].y);l+=3;}sort (g,g+l,cmp);int ans=0;ft(i,0,l-1){dp[i]=g[i].h;for (int j=0;j<i;j++){if (g[j].x<g[i].x&&g[j].y<g[i].y&&dp[i]<dp[j]+g[i].h)dp[i]=dp[j]+g[i].h;}ans=max(ans,dp[i]);}printf("Case %d: maximum height = %d\n",ca++,ans);} }

總結

以上是生活随笔為你收集整理的uva 437——The Tower of Babylon的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。