HDU1069(最长单调递减数列) - c++编程基础

告诉你n种规模的长方体的长，宽，高，每种规模的长方体个数不限，问你最多能搭多高的塔，塔是由这些长方体搭的，自上而下，每一块长方体都要比在它下面的长方体的规模小，即长和宽都比下面的长方体要小。注意长方体是可以调整的。

就是按照长和宽来排序，找最长的单调递减的数列。我们用dp[i]来表示搭建到第i块长方体的时候塔的最高高度，那么状态转移方程就是dp[i]=max(dp[i],dp[j]+s[i].h)；

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #define M 100000+5 #define LL long long #define Ld __int64 #define eps 0.00001 #define INF 999999999 #define MOD 112233 #define MAX 26 #define PI acos(-1.0) using namespace std; struct solid { int l,w,h; }s[155]; bool cmp(solid a,solid b) { if(a.l==b.l) { if(a.w==b.w) return a.h>b.h; return a.w>b.w; } return a.l>b.l; } int main() { int n,cont=1; int d[3]; int dp[155]; while(~scanf("%d",&n),n) { int k=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&d[0],&d[1],&d[2]); sort(d,d+3); s[k].l=d[2],s[k].w=d[1],s[k++].h=d[0]; //各种长方体 s[k].l=d[2],s[k].w=d[0],s[k++].h=d[1]; s[k].l=d[1],s[k].w=d[0],s[k++].h=d[2]; } sort(s,s+k,cmp); for(int i=0;i
             
              =0;i--) { for(int j=i+1;j
              
               s[j].l && s[i].w>s[j].w) { dp[i]=max(dp[i],dp[j]+s[i].h); } } } int ans=-1; for(int i=0;i