Submit Time:2024-04-03 14:39:38

运行 ID: 141345

#include<bits/stdc++.h> using namespace std; const int maxn = 10010; int f[maxn],g[maxn],res[maxn]; struct node{ int a,b,f; }p[maxn]; bool cmp(node x,node y){ if(x.a != y.a) return x.a < y.a; return x.b < y.b; } int main(){ int n;cin >> n; for(int i = 1;i <= n;i ++){ int a,b;cin >> a >> b; p[i] = {a,b,i}; f[i] = 1; } sort(p + 1,p + 1 + n,cmp); ///for(int i = 1;i <= n;i ++) ///cout << p[i].a << " " << p[i].b << " " << p[i].f << endl; for(int i = 1;i <= n;i ++){ for(int j = 1;j < i;j ++){ if(p[i].a > p[j].a && p[i].b > p[j].b){ if(f[i] < f[j] + 1){ f[i] = f[j] + 1; g[p[i].f] = p[j].f; } /// else if(f[i] == f[j] + 1 && g[p[i].f] > p[j].f) ///g[p[i].f] = p[j].f; } } } int ans = 0,id; for(int i = 1;i <= n;i ++){ if(f[i] > ans){ ans = f[i]; id = p[i].f; } } int tot = 0; res[++ tot] = id; while(g[id]){ res[++ tot] = g[id]; id = g[id]; } cout << ans << endl; for(int i = tot;i >= 1;i --) cout << res[i] << " "; return 0; }