本文主要是介绍nyoj232 How to eat more Banana dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是给n种长方体长宽高分别为x，y，z，每种长方体的数量为无限个。
求长方体叠放的最大高度。上面的长方体的长和宽必须小于下面的长和宽，不能等于。
可以任意摆放长方体，也就是每种长方体就有六种情况。
先将长方体按长和宽的降序排好，然后按照最长递增子序列的思路，用dp[]存储当前长方体可以叠加的最大高度。
#include <bits/stdc++.h>
using namespace std;
struct blocks{int x,y,z;
}l[200];//每种物体都有六种状态
bool cmp(blocks a,blocks b){if(a.x==b.x) return a.y>b.y;return a.x>b.x;
}
int main(){int n;int dp[200];int kk=1;while(cin>>n){if(!n) break;memset(dp,0,sizeof(dp));int x,y,z;int k=-1;while(n--){cin>>x>>y>>z;l[++k].x=x; l[k].y=y; l[k].z=z;l[++k].x=y; l[k].y=x; l[k].z=z;l[++k].x=z; l[k].y=x; l[k].z=y;l[++k].x=x; l[k].y=z; l[k].z=y;l[++k].x=y; l[k].y=z; l[k].z=x;l[++k].x=z; l[k].y=y; l[k].z=x;}sort(l,l+k+1,cmp);//这里+1因为k是末尾,sort要求第二个参数是末尾+1int maxx=-1;dp[0]=l[0].z;for(int i=1;i<=k;i++){dp[i]=l[i].z;for(int j=0;j<=i;j++){if(l[i].x<l[j].x&&l[i].y<l[j].y)dp[i]=max(dp[i],dp[j]+l[i].z);}}for(int i=0;i<=k;i++)maxx=max(dp[i],maxx);cout<<"Case "<<(kk++)<<": maximum height = "<<maxx<<endl;}
}
这篇关于nyoj232 How to eat more Banana dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
