UVa 103 - Stacking Boxes

　　题目大意：矩阵嵌套，不过维数是多维的。有两个个k维的盒子A(a₁, a₁...a_k), B(b₁, b₂...b_k)，若能找到(a₁...a_k)的一个排列使得a_i< b_i，则盒子A可嵌套在盒子B中。给出n个k维的盒子，找出最长的可嵌套的盒子的序列。实际上是DAG上的动态规划问题。首先是判断A能否嵌套在B中，对盒子的k维数进行排序，依次比较即可。然后用d[i]表示以节点i为起点的最长路径的长度，可以得到状态转移方程：d(i) = max{d(j)+1}, (i,j)是图上的一条边。最后就是打印路径，根据转移方程递归打印路径即可。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define BOXN 35

 #define DIMENSION 12

 int k, n;    // k is the number of boxes, n is the dimensionality

 int box[BOXN][DIMENSION], d[BOXN];    // d[i] save the number of nodes in the longest path starting with node i

 int G[BOXN][BOXN];

 bool is_nested(int *box1, int *box2)

 {

     // if box1 can be nested in box2, return true; otherwise false

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

         if (box1[i] >= box2[i])   return false;

     return true;

 }

 int dp(int i)    // compute d[i]

 {

     if (d[i] > )   return d[i];

     d[i] = ;

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

         if (G[i][j])

             d[i] = max(d[i], dp(j)+);

     return d[i];

 }

 void print_path(int i)    // print the longest path starting with node i

 {

     printf("%d ", i);

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

         if (G[i][j] && d[i] == d[j]+)

         {

             print_path(j);

             break;

         }

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif

     while (scanf("%d%d", &k, &n) != EOF)

     {

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

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

                 scanf("%d", &box[i][j]);

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

             sort(box[i], box[i]+n);

         memset(G, , sizeof(G));

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

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

                 if (is_nested(box[i], box[j]))

                     G[i][j] = ;

         int ans = -;

         int start = ;

         memset(d, , sizeof(d));

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

         {

             int t = dp(i);

             if (t > ans)

             {

                 ans = t;

                 start = i;

             }

         }

         printf("%d\n", ans);

         print_path(start);

         printf("\n");

     }

     return ;

 }

巴特西

UVa 103 - Stacking Boxes

最新文章

热门文章