// UVa 103 - Stacking Boxes #include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; int n, d; struct box { int a; int s[10]; }; bool operator <(const box & a, const box & b) { for (int j = 0; j < d; j++) if (a.s[j] != b.s[j]) return a.s[j] < b.s[j]; return true; } bool inside(const box & a, const box & b) { for (int j = 0; j < d; j++) if (a.s[j] >= b.s[j]) return false; return true; } int main() { while (cin >> n >> d) { box b[30]; for (int i = 0; i < n; i++) { for (int j = 0; j < d; j++) cin >> b[i].s[j]; b[i].a = i + 1; sort(b[i].s, b[i].s + d); } sort(b, b + n); int T[30], R[30]; int sol = 0; for (int i = 0; i < n; i++) { T[i] = 0; R[i] = -1; for (int j = 0; j < i; j++) { if (inside(b[j], b[i]) && T[j] > T[i]) { T[i] = T[j]; R[i] = j; } } T[i]++; if (T[i] > T[sol]) sol = i; } cout << T[sol] << endl; stack<int> s; while (sol != -1) { s.push(sol); sol = R[sol]; } while (s.size() > 1) { cout << b[s.top()].a << " "; s.pop(); } cout << b[s.top()].a << endl; } }
Saturday, June 6, 2015
UVa 103 - Stacking Boxes
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment