UVA 437 The Tower of Babylon（DAG上的动态规划）

题目大意是根据所给的有无限多个的n种立方体，求其所堆砌成的塔最大高度。

方法1，建图求解，可以把问题转化成求DAG上的最长路问题

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn = ;

 struct Node{

     int x;

     int y;

     int z;

     Node(int x,int y,int z):x(x),y(y),z(z){}

     Node(){}

     bool operator < (const Node &n)const{

         return (x < n.x&& y < n.y) || (x < n.y&& y < n.x);

     }

 };

 vector<Node> vec;

 int n;

 int d[maxn*];

 int G[maxn*][maxn*];

 int dp(int i,int h){

     int & ans = d[i];

     if(ans>)return ans;

     ans = h;

     for(int j = ; j < n*; j++)if(G[i][j]){

         ans = max(ans,dp(j,vec[j].z)+h);

     }

     return ans;

 }

 int main(){

     int cnt = ;

     while(scanf("%d",&n)==&&n){

         vec.clear();

         memset(G,,sizeof(G));

         memset(d,,sizeof(d));

         for(int i = ; i< n; i++){

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             vec.push_back(Node(x,y,z));

             vec.push_back(Node(x,z,y));

             vec.push_back(Node(z,y,x));

         }

         sort(vec.begin(),vec.end());

         for(int i = ;i < n*; i++){

             for(int j = ; j < n*; j++){

                 if(vec[i] < vec[j])

                     G[i][j] = ;

             }

         }

         int result = -;

         for(int i = ; i < n* ;i++){

             result = max(result,dp(i,vec[i].z));

         }

         printf("Case %d: maximum height = %d\n",++cnt,result);

     }

     return ;

 }

方法2，转化成最长递增子序列问题求解

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn = ;

 struct Node{

     int x;

     int y;

     int z;

     Node(int x,int y,int z):x(x),y(y),z(z){}

     Node(){}

     bool operator < (const Node &n)const{

         return (x < n.x&& y < n.y) || (x < n.y&& y < n.x);

     }

 };

 bool cmp(Node a,Node b){

     return a.x*a.y < b.x*b.y;

 }

 vector<Node> vec;

 int n;

 int d[maxn*];

 int LIS(int n){

     //d[i] = max{hi,d[j]}i>j ,A[i]>A[j]

     int t = ;

     for(int i = ; i < n*; i++){

         d[i] = vec[i].z;

         for(int j = ; j < i; j++)

             if(vec[j] < vec[i])

                 d[i] = max(d[i],d[j]+vec[i].z);

         if(d[i] > t) t = d[i];

     }

     return t;

 }

 int main(){

     int cnt = ;

     while(scanf("%d",&n)==&&n){

         vec.clear();

         memset(d,,sizeof(d));

         for(int i = ; i< n; i++){

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             vec.push_back(Node(x,y,z));

             vec.push_back(Node(x,z,y));

             vec.push_back(Node(z,y,x));

         }

         sort(vec.begin(),vec.end(),cmp);

         printf("Case %d: maximum height = %d\n",++cnt,LIS(n));

     }

     return ;

 }

方法二要注意一点，我sort序列的时候用了一个cmp函数，他是根据立方体的底面积对立方体进行排序的。为什么不采用和方法一一样的排序方式呢？

因为a.x <b.x&&a.y<b.y

或 a.y<b.x&&a.x<b.y

=>Sa <Sb

所以在塔上面的立方体的底面积一定比下面的小。