hdu1069线性dp

/* dp[i]：取第i个方块时最多可以累多高 */ #include<bits/stdc++.h> using namespace std; struct node{ int x,y,z; bool operator<(const node & a)const { if(x==a.x)return y>a.y; return x>a.x; } //按照x从大到小排，x相同的话就按y从小到大排 }block[1000]; int dp[1000],tot; int main(){ int x,y,z,n,tt=0; while(scanf("%d",&n),n){ tt++;tot=0; memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){//最多有六种形态，能够保证一个块不会以两个形态被使用两次 scanf("%d%d%d",&x,&y,&z); block[++tot].x=x;block[tot].y=y;block[tot].z=z; block[++tot].x=y;block[tot].y=x;block[tot].z=z; block[++tot].x=y;block[tot].y=z;block[tot].z=x; block[++tot].x=z;block[tot].y=y;block[tot].z=x; block[++tot].x=z;block[tot].y=x;block[tot].z=y; block[++tot].x=x;block[tot].y=z;block[tot].z=y; } sort(block+1,block+1+tot); dp[1]=block[1].z; for(int i=2;i<=tot;i++){ int Max=0; for(int j=1;j<i;j++){ if(block[i].x<block[j].x && block[i].y<block[j].y) Max=max(Max,dp[j]);//找出高度最大的基底 　　　　//dp[i]=max(dp[i],dp[j]+block[i].z);为什么不可以这样？　　　　　　　} dp[i]=Max+block[i].z; } int ans=0; for(int i=1;i<=tot;i++)ans=max(ans,dp[i]); printf("Case %d: maximum height = %d\n",tt,ans); } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/10280274.html