首页 > 代码库 > POJ 2241 The Tower of Babylon(UVA 437)
POJ 2241 The Tower of Babylon(UVA 437)
多种方法,我用DP做的。
我当成的 最长下降子序列做的。 问了下其他人,有树形DP的,有差分约束用最短路的。
还有当作 二维的背包问题的。
最长单调子序列,长宽高 x,y,z 分别枚举成六个。然后排序,找最长单调子序列即可。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<bitset> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i<b;i++) #define FOR_(i,a,b) for(int i=a;i>=b;i--) #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE 200 +1 using namespace std; struct point { int x,y,z; void init(int xx,int yy,int zz) { x=xx,y=yy,z=zz; } friend bool operator <(point a,point b) { if(a.x==b.x) { if(a.y==b.y) return a.z>b.z; return a.y>b.y; } return a.x>b.x; } }l[SIZE]; int n; int dp[SIZE]; int main() { int cs=1; while(~sf("%d",&n),n) { int m=0; FOR(i,0,n) { int x,y,z; sf("%d%d%d",&x,&y,&z); l[m++].init(x,y,z); l[m++].init(x,z,y); l[m++].init(y,x,z); l[m++].init(y,z,x); l[m++].init(z,x,y); l[m++].init(z,y,x); } sort(l,l+m); CLR(dp,0); FOR(i,0,m) { FOR(j,i+1,m) { if(l[j].x<l[i].x&&l[j].y<l[i].y) dp[j]=max(dp[j],dp[i]+l[i].z); } } int ans=0; FOR(i,0,m) //pf("%d \n",dp[i]+l[i].z); ans=max(ans,dp[i]+l[i].z); pf("Case %d: maximum height = %d\n",cs++,ans); } }
POJ 2241 The Tower of Babylon(UVA 437)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。