2012年9月6日

UVa 103 - Stacking Boxes


#include <stdio.h>
#include <stdlib.h>

typedef struct Box Box;

struct Box {
  int index;
  int num[10];
};

int big(Box a, Box b, int s) {
  int i;
  for (i = 0; i < s; i++)
    if (a.num[i] <= b.num[i]) return 0;
  return 1;
};

int cmpInt(const void* a, const void* b) {
  return *(int *)a - *(int *)b;
};

int cmpBox(const void* a, const void* b) {
  return (*(Box *)a).num[0] - (*(Box *)b).num[0];
};

void print(int pos, int* prev, Box* box, int ans) {
  if (prev[pos] != -1) print(prev[pos], prev, box, ans - 1);
  printf("%d", box[pos].index);
  if (ans) printf(" ");
}

int main() {
  int i, j, n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    Box *box = malloc(n * sizeof(Box));
    for (i = 0; i < n; i++) {
      box[i].index = i + 1;
      for (j = 0; j < m; j++)
        scanf("%d", &box[i].num[j]);
      qsort(box[i].num, m, sizeof(int), cmpInt);
    }
    qsort(box, n, sizeof(Box), cmpBox);
    int *dp = malloc(n * sizeof(int)), *prev = malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
      dp[i] = 1;
      prev[i] = -1;
    }
    for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++)
        if (big(box[j], box[i], m))
          if (dp[i] + 1 > dp[j]) {
            dp[j] = dp[i] + 1;
            prev[j] = i;
          }
    int ans = 0, pos = 0;
    for (i = 0; i < n; i++)
      if (dp[i] > ans) {
        ans = dp[i];
        pos = i;
      }
    printf("%d\n", ans);
    print(pos, prev, box, ans);
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言