uva 103 经典DAG变形

https://vjudge.net/problem/UVA-103

也是一个经典的DAG模型，因为书上的翻译和原文不照导致WA两发= =

对于同一维度的两个箱子A，B，A可以嵌套在B中的一个充分条件是A所有的边长和 < B所有的边长和，先根据边长和进行排序，在比较A是否能嵌套于B中时，把两个箱子的边长按升序排列后一一对比只要均满足A<B就说明A可以嵌套与B中。

 #include<bits/stdc++.h>

 using namespace std;

 int V,N,f[];

 struct box

 {

     int s,u;

     int a[];

     void show()

     {

         for(int i=;i<=V;++i) printf("%d ",a[i]);puts("");

     }

 }P[];

 bool cmp(box A,box B){return A.s<B.s;}

 bool ok(box A,box B)

 {

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

         if(A.a[i]>=B.a[i]) return ;

     return ;

 }

 int main()

 {

     int i,j,k;

     int path[];

     while(cin>>N>>V){int ans=;

     memset(path,-,sizeof(path));

         for(i=;i<=N;++i)

         {

             P[i].s=;

             P[i].u=i;

             for(j=;j<=V;++j)

             {

                 scanf("%d",&P[i].a[j]);

                 P[i].s+=P[i].a[j];

             }

             sort(P[i].a+,P[i].a++V);

         }

         memset(f,,sizeof(f));

         sort(P+,P++N,cmp);

         for(i=;i<=N;++i)

         {

             int maxn=,u=i;

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

             {

                 if(ok(P[j],P[i])&&f[j]>maxn){

                     maxn=f[j];

                     u=j;

                 }

             }

             path[i]=u;

             f[i]=maxn+;

             ans=max(ans,f[i]);

         }

         stack<int>T;

         int x=ans;

         for(i=N;i;--i)

         {

             if(f[i]==ans){

                 int u=i;

             while(T.empty()||u!=T.top()){

                 T.push(u);

                 u=path[u];

             }

                 break;

             }

         }

         printf("%d\n%d",ans,P[T.top()].u);T.pop();

         while(!T.empty()){

             printf(" %d",P[T.top()].u);

             T.pop();

         }

         puts("");

     }

     return ;

 }