UVA 103 Stacking Boxes n维最长上升子序列

题目链接：UVA - 103

题意：现有k个箱子，每个箱子可以用n维向量表示。如果一个箱子的n维向量均比另一个箱子的n维向量大，那么它们可以套接在一起，每个箱子的n维向量可以互相交换值，如箱子（2，6）可以和箱子（7，3）套接在一起。求出套接的箱子最多的个数前提下任意一种解决方案。

算法：抛开n维不看，本题就是一个DP的最长上升子序列问题，现在加上了n维的限制，想想也不是很难吧，在DP过程中判断每一维都满足条件即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define inf 0x7fffffff

 using namespace std;

 typedef long long LL;

 int k,n;

 int dp[],pre[];

 struct node

 {

     int an[];

     int id;

     friend bool operator < (node a,node b)

     {

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

         {

             if (a.an[i] != b.an[i]) return a.an[i] <  b.an[i];

         }

     }

 }arr[];

 void printOut(int u)

 {

     if (pre[u]!=-) printOut(pre[u]);

     if (pre[u]==-) printf("%d",arr[u].id+ );

     else printf(" %d",arr[u].id+ );

 }

 int main()

 {

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

     {

         memset(dp,,sizeof(dp));

         memset(pre,-,sizeof(pre));

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

         {

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

                 scanf("%d",&arr[i].an[j]);

             arr[i].id=i;

             sort(arr[i].an,arr[i].an+n);

         }

         sort(arr,arr+k);

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

 //        {

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

 //                cout<<arr[i].an[j]<<" ";

 //            cout<<endl;

 //        }

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

         {

             int temp=;

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

             {

                 int flag=;

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

                     if (arr[i].an[u]<=arr[j].an[u]) {flag=;break; }

                 if (!flag && dp[j]>temp)

                 {

                     temp=dp[j];

                     pre[i]=j;

                 }

             }

             dp[i]=temp+;

         }

         int maxlen=-,num=;

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

         {

             if (dp[i]>maxlen)

             {

                 maxlen=dp[i];

                 num=i;

             }

         }

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

         printOut(num);

         printf("\n");

     }

     return ;

 }

巴特西

UVA 103 Stacking Boxes n维最长上升子序列

最新文章

热门文章