相關的教學可以看這裡
之前想說應該是做3個sort,
先對維度做sort,接著對每個維度的第一個維度sort,
接著把所有的box依照sort就有解。
後來想想好像不對……
所以第三步驟其實不是作sort,是做LIS。
把整個題目想成是一個box lis就很簡單了。
單一個box由n個維度構成,所以box的大小由n個維度所決定。
而維度內先排列是必要的(因為要跟其他box比大小)
而題目要作最多的「大包小」的動作。
所以先把每個box依照大小順序做排列也是必要的。
如此小的在前面,大的在後面,才可以找出最多的「大包小」。
/* ACM 103 Stacking Boxes * mythnc * 2012/01/15 14:42:45 * run time: 0.008 */ #include <stdio.h> #include <stdlib.h> #define MAXBOX 30 #define MAXD 10 typedef struct box { int num; int dimen[MAXD]; } Box; void init(int, int); int cmpd(const void *, const void *); int cmpb(const void *, const void *); int lis(int, int); void output(int); Box b[MAXBOX]; int len[MAXBOX], pre[MAXBOX]; int main(void) { int n, d; while (scanf("%d %d", &n, &d) == 2) { init(n, d); output(lis(n, d)); } return 0; } /* init: receive input data, initialize b content, * and sort data */ void init(int n, int d) { int i, j; for (i = 0; i < n; i++) { b[i].num = i + 1; len[i] = 1; pre[i] = -1; for (j = 0; j < d; j++) scanf("%d", &b[i].dimen[j]); qsort(b[i].dimen, d, sizeof(int), cmpd); } qsort(b, n, sizeof(Box), cmpb); } /* cmpd: sort dimension for qsort() */ int cmpd(const void *a, const void *b) { return *(int *)a - *(int *)b; } /* cmpb: sort dimen[0] for qsort() */ int cmpb(const void *a, const void *b) { return ((Box *)a)->dimen[0] - ((Box *)b)->dimen[0]; } /* lis: find longest increasing subsequence. * the unit is "box" * return its pos */ int lis(int n, int d) { int i, j, k, maxi; for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) { for (k = 0; k < d && b[j].dimen[k] > b[i].dimen[k]; k++) ; if (k == d && len[i] + 1 > len[j]) { len[j] = len[i] + 1; pre[j] = i; } } for (i = 1, maxi = 0; i < n; i++) if (len[i] > len[maxi]) maxi = i; return maxi; } /* output: output lis len and seq */ void output(int i) { int num; int inc[MAXBOX]; /* output max lis len */ printf("%d\n", len[i]); num = 0; while (1) { inc[num++] = b[i].num; if (pre[i] == -1) break; i = pre[i]; } /* out lis seq */ printf("%d", inc[--num]); for (i = num - 1; i > -1; i--) printf(" %d", inc[i]); putchar('\n'); }
沒有留言:
張貼留言