#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2012年9月6日
UVa 103 - Stacking Boxes
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言