ｎ个老鼠，分别给出这ｎ个老鼠的质量和速度，让你选出其中的ｋ个老鼠，使得这ｋ个老鼠的质量按严格递增排列，速度按严格递减排列．

将其中一个速度字段递减排序，然后求质量的最长上升子序列就好了．需要记录其路径．记录路径只能用 O(n^2) 的算法，用 O(n\\log(n))的算法记录不了路径．

这题的 SPJ 有毒吧，我求出路径后，顺着输出会 WA，非得从后往前输出，不然代码中我也不会用 stack 来保存了．

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct node {
    int s, v, id;
    bool operator < (const node &op) const {
        return v > op.v;
    }
} e[N];
int rec[N], dp[N];
int main()
{
    int m = 1;
    while (~scanf("%d %d", &e[m].s, &e[m].v)) {
        e[m].id = m;
        m++;
    }
    m--;
    sort(e + 1, e + m + 1);
    int mx = 0, pos = 0;
    for (int i = 1; i <= m; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (e[i].s > e[j].s && e[i].v < e[j].v && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                rec[i] = j;
            }
        }
        if (dp[i] > mx) {
            mx = dp[i];
            pos = i;
        }
    }
    stack<int> ans;
    while (pos) {
        ans.push(pos);
        pos = rec[pos];
    }
    printf("%d\n", ans.size());
    while (!ans.empty()) {
        printf("%d\n", e[ans.top()].id);
        ans.pop();
    }
    return 0;
}