Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
141345 | YYYY | 和谐俱乐部 | C++ | 解答错误 | 0 | 3 MS | 292 KB | 1315 | 2024-04-03 14:39:38 |
#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; }