UVA_103

    首先我们应该对坐标内部排序，之后一个直观的想法就是扫描一遍所有盒子，如果i可以放到j内，就连一条i->j的有向边，然后求dfs树形图的最深层数即可。

    另外，我们也可以对盒子按第一个坐标进行排序，然后去求最长上升子序列。

#include
     
       #include
      
        #include
       
         int N, K, G[40][40], a[40][20], indgr[40], outdgr[40], path[40], max; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p; int *q = (int *)_q; return *p - *q; } int suit(int i, int j) {
   int k; for(k = 0; k < K; k ++) if(a[i][k] >= a[j][k]) return 0; return 1; } int dfs(int cur, int num) {
   int i, j, ok; if(outdgr[cur] == 0)     {
   if(num > max)         {
               max = num;             path[num] = cur; return 1;         } return 0;     }     ok = 0; for(i = 0; i < N; i ++) if(G[cur][i] && dfs(i, num + 1))         {
               path[num] = cur;             ok = 1;         } return ok; } void init() {
   int i, j; for(i = 0; i < N; i ++)     {
   for(j = 0; j < K; j ++)             scanf("%d", &a[i][j]);         qsort(a[i], K, sizeof(a[i][0]), cmp);     }     memset(G, 0, sizeof(G));     memset(indgr, 0, sizeof(indgr));     memset(outdgr, 0, sizeof(outdgr)); for(i = 0; i < N; i ++) for(j = 0; j < N; j ++) if(suit(i, j))             {
                   G[i][j] = 1;                 outdgr[i] ++;                 indgr[j] ++;             } } void solve() {
   int i;     max = 0; for(i = 0; i < N; i ++) if(!indgr[i])             dfs(i, 1);     printf("%d\n", max); for(i = 1; i <= max; i ++)     {
   if(i > 1)             printf("");         printf("%d", path[i] + 1);     }     printf("\n"); } int main() {
   while(scanf("%d%d", &N, &K) == 2)     {
           init();         solve();     } return 0; }
       
      
     

 

#include
     
       #include
      
        #include
       
         int N, K, r[40], f[40], a[40][20], fa[40]; int cmp1(const void *_p, const void *_q) {
   int *p = (int *)_p; int *q = (int *)_q; return *p - *q; } int cmp2(const void *_p, const void *_q) {
   int *p = (int *)_p; int *q = (int *)_q; return a[*p][0] - a[*q][0]; } int suit(int i, int j) {
   int k; for(k = 0; k < K; k ++) if(a[i][k] >= a[j][k]) return 0; return 1; } void init() {
   int i, j; for(i = 0; i < N; i ++)     {
   for(j = 0; j < K; j ++)             scanf("%d", &a[i][j]);         qsort(a[i], K, sizeof(a[i][0]), cmp1);     } for(i = 0; i < N; i ++)         r[i] = i;     qsort(r, N, sizeof(r[0]), cmp2); } void printresult(int cur) {
   if(fa[cur] == -1)         printf("%d", r[cur] + 1); else     {
           printresult(fa[cur]);         printf(" %d", r[cur] + 1);     } } void solve() {
   int i, j, max, p; for(i = 0; i < N; i ++)         f[i] = 1;     memset(fa, -1, sizeof(fa)); for(i = 0; i < N; i ++) for(j = 0; j < i; j ++)         {
   if(suit(r[j], r[i]) && f[j] + 1 > f[i])             {
                   f[i] = f[j] + 1;                 fa[i] = j;             }         }     max = 0; for(i = 0; i < N; i ++) if(f[i] > max)         {
               max = f[i];             p = i;         }     printf("%d\n", max);     printresult(p);     printf("\n"); } int main() {
   while(scanf("%d%d", &N, &K) == 2)     {
           init();         solve();     } return 0; }