HUD 1160 FatMouse's Speed——LIS

HUD 1160 FatMouse's Speed——LIS

这题貌似不是严格上升下降的，把相等的情况考虑进就AC了

另外用nlogn算法打印时只需要让当前的id指向辅助数组中前一个位置的id即可

#include #include #include #include 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]);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。