|
|
back to board#include <cstdio> #include <cstring> #include <cmath> using namespace std; int a[501][3], f[501], trace[501], n, ans, t; void sort(int l, int r) { int x = a[(l + r) >> 1][0]; int i, j, t[3]; i = l; j = r; do { while (a[i][0] < x) i++; while (a[j][0] > x) j--; if (i <= j) { memcpy(t, a[i], sizeof(t)); memcpy(a[i], a[j], sizeof(t)); memcpy(a[j], t, sizeof(t)); } i++; j--; } while (i <= j); if (i < r) sort(i, r); if (l < j) sort(l, j); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d", &a[i][0], &a[i][1]); a[i][2] = i; } for (int i = 1; i <= n; i++) f[i] = 1; sort(1, n); for (int i = 2; i <= n; i++) for (int j = 1; j < i; j++) if ((a[j][0] < a[i][0]) && (a[j][1] > a[i][1]) && (f[j] + 1 > f[i])) { f[i] = f[j] + 1; trace[i] = j; } ans = 0; t = 0; for (int i = 1; i <= n; i++) if (f[i] > ans) { ans = f[i]; t = i; }; printf("%d\n", ans); while (t != 0) { printf("%d ", a[t][2]); t = trace[t]; } return 0; } |
|
|