题目
求一个二维的严格递增序列。我们先排个序，然后再dp严格递增子序列，记录一下是从哪里转移过来的。然后再递归输出路径即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const double Pi = acos(-1); namespace { template <typename T> inline void read(T &x) { x = 0; T f = 1; char s = getchar(); for(; !isdigit(s); s = getchar()) if(s == '-') f = -1; for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48); x *= f; } } #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define _srep(n,m,i)for (register int i = (n); i >= (m); i--) #define _sfor(n,m,i)for (register int i = (n); i > (m); i--) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) x & (-x) #define pii pair<int,int> #define fi first #define se second const int N = 5e3+5; struct node { int w, h, id; bool operator < (const node &x) const { return w == x.w ? h < x.h : w < x.w; } } e[N]; int dp[N], pos[N]; void print(int x) { if(!x) return ; print(pos[x]); printf("%d ", e[x].id); } int main() { int n, w, h, cnt = 0; read(n);read(w);read(h); for(int i = 1; i <= n; i++) { read(e[0].w);read(e[0].h);e[0].id = i; if(e[0].w > w && e[0].h > h) e[++cnt] = e[0]; } if(!cnt) return 0*puts("0"); int ans = 0, st = 0; e[0].h = e[0].id = e[0].w = 0; sort(e + 1, e + cnt + 1); for(int i = 1; i <= cnt; i++) for(int j = 0; j < i; j++) if(e[i].w > e[j].w && e[i].h > e[j].h) { if(dp[i] < dp[j] + 1) dp[i] = dp[j]+1, pos[i] = j; if(dp[i] > ans) ans = dp[i], st = i; } printf("%d\n", ans); print(st); }