#UVa：103－Stacking Boxes

先對每個Box的長度做排序，再對全部Box的序列做排序，接著用LIS(Longest Increasing Subsequence)的方法即可得解。

C++(0.016)

/*******************************************************/
/* UVa 103 Stacking Boxes                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2015/01/14                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Box{
  int id;
  vector<int> length;

  Box(int i = 0, int n = 0, int value = 0){
    id = i;
    length = vector<int>(n, value);
  }
};

bool boxCompare(const Box &a, const Box &b){
  for( int i = 0 ; i < a.length.size() ; ++i ){
    if( a.length[i] < b.length[i] ) return true;
    if( a.length[i] > b.length[i] ) return false;
  }
  return true;
}


bool isBoxContain(const Box &a, const Box &b){
  for( int i = 0 ; i < a.length.size() ; ++i ){
    if( a.length[i] <= b.length[i] ) return false;
  }
  return true;
}

void printNestingBox(const vector<int> &prevNesting, const vector<Box> &boxSequence, int lastbox, bool printSpace){
  if( lastbox == -1 ) return ;

  printNestingBox( prevNesting, boxSequence, prevNesting[lastbox], true );
  printf("%d", boxSequence[lastbox].id);
  if( printSpace ) printf(" ");
}

int main(){
  int k, n;
  while( scanf("%d%d", &k, &n) != EOF ){
    
    vector<Box> boxSequence;
    for( int i = 0 ; i < k ; ++i ){
      Box box(i+1, n, 0);
      for( int j = 0 ; j < n ; ++j ){
        scanf("%d", &(box.length[j]));
      }
      sort( box.length.begin(), box.length.end() );
      boxSequence.push_back(box);
    }
    
    sort( boxSequence.begin(), boxSequence.end(), boxCompare );

    vector<int> maxNesting(k, 1), prevNesting(k, -1);
    int maxlength = 1, lastbox = 0;
    for( int i = 0 ; i < boxSequence.size() ; ++i ){
      for( int j = 0 ; j < i ; ++j ){
        if( isBoxContain(boxSequence[i], boxSequence[j]) ){
          if( maxNesting[j]+1 > maxNesting[i] ){
            maxNesting[i] = maxNesting[j] + 1;
            prevNesting[i] = j;
            if( maxNesting[i] > maxlength ){
              maxlength = maxNesting[i];
              lastbox = i;
            }
          }
        }
      }
    }

    printf("%d\n", maxlength);
    printNestingBox(prevNesting, boxSequence, lastbox, false);
    printf("\n");
  }
  return 0;
}