首页 > 代码库 > uva 437 The Tower of Babylon(动态规划 嵌套矩形问题最长路)
uva 437 The Tower of Babylon(动态规划 嵌套矩形问题最长路)
有思路就去做,要相信自己
多处理更复杂的情况,你就不觉得现在复杂了
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; struct soli { ll a,b,c; }s[40]; int n; ll d[40][3]; int vis[40][3]; ll answer[40][3]; ll dp(int s1,int s2) { if(vis[s1][s2]) return d[s1][s2]; vis[s1][s2]=1; ll& ans=d[s1][s2]; ll temp1,temp2; if(s2==0){temp1=s[s1].b;temp2=s[s1].c;ans=s[s1].a;} if(s2==1){temp1=s[s1].a;temp2=s[s1].c;ans=s[s1].b;} if(s2==2){temp1=s[s1].a;temp2=s[s1].b;ans=s[s1].c;} ll temp=ans; for(int i=1;i<=n;i++) { for(int j=0;j<=2;j++) { if(j==0) { if((s[i].b<temp1&&s[i].c<temp2)||(s[i].b<temp2&&s[i].c<temp1)) { ans=max(ans,dp(i,j)+temp); } } if(j==1) { if((s[i].a<temp1&&s[i].c<temp2)||(s[i].a<temp2&&s[i].c<temp1)) { ans=max(ans,dp(i,j)+temp); } } if(j==2) { if((s[i].b<temp1&&s[i].a<temp2)||(s[i].b<temp2&&s[i].a<temp1)) { ans=max(ans,dp(i,j)+temp); } } } } return ans; } int main() { int kase=0; while(scanf("%d",&n)!=EOF) { if(n==0) break; kase++; ll a1,a2,a3; memset(s,0,sizeof(s)); for(int i=1;i<=n;i++) { scanf("%I64d%I64d%I64d",&a1,&a2,&a3); s[i].a=a1; s[i].b=a2; s[i].c=a3; } memset(answer,0,sizeof(answer)); for(int i=1;i<=n;i++) { for(int j=0;j<=2;j++) { memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); answer[i][j]=dp(i,j); } } ll max_=0; for(int i=1;i<=n;i++) { for(int j=0;j<=2;j++) { max_=max(max_,answer[i][j]); } } printf("Case %d: maximum height = %I64d\n",kase,max_); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。