这题貌似不是严格上升下降的，把相等的情况考虑进就AC了
另外用nlogn算法打印时只需要让当前的id指向辅助数组中前一个位置的id即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1010; struct Mice { int w, s, id; bool operator < (const Mice &t) { if (s != t.s) return s > t.s; return w < t.w; } }mice[maxn]; int w, s, n, a[maxn], id[maxn], pre[maxn]; int LIS() { int cnt = 0, minv = INF; for (int i = 1; i <= n; i++) { // if (mice[i].s == minv) continue; // minv = mice[i].s; if (mice[i].w > a[cnt]) { a[++cnt] = mice[i].w; id[cnt] = mice[i].id; pre[mice[i].id] = id[cnt - 1]; } else { int pos = lower_bound(a + 1, a + 1 + cnt, mice[i].w) - a; a[pos] = mice[i].w; id[pos] = mice[i].id; pre[mice[i].id] = id[pos - 1]; } } return cnt; } void output(int x) { if (x == 0) return; output(pre[x]); printf("%d\n", x); } int main() { while (~scanf("%d %d", &w, &s)) { mice[++n].w = w, mice[n].s = s, mice[n].id = n; } sort(mice + 1, mice + 1 + n); int ans = LIS(); printf("%d\n", ans); output(id[ans]); }