#UVa:103-Stacking Boxes

灆洢 2015-01-14 19:59:39

先對每個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;
}

在〈“#UVa:103-Stacking Boxes”〉中有 2 則留言

  1. 梁again表示:

    原本這題做不出來, 想上網找看看有沒有參考解.最後找到這篇.感謝你給的範例
    但因為boxCompare 那邊輸進sort會導致 comparator error(兩個同樣大小的box 前一次跟後一次比較大小不一樣),我把它改了一下
    bool boxCompare(const Box& a, const Box& b) {
    ………
    if(a.id < b.id)
    return true;
    else {
    return false;
    }
    }

    最後Uva submit 是有 AC的.

    • 灆洢表示:

      感謝!XD

      我之後應該會再整理一下之前寫的題目,
      到時候我再補充上去。

灆洢 發表迴響 取消回覆

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料