解题思路:转化为最长不下降子序列
注意事项:
参考代码:
#include<iostream> #include<utility> #include<algorithm> using namespace std; const int N = 5e3 + 10; pair<int,int> p[N]; int n, a[N],f[N]; int main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> p[i].first >> p[i].second; sort(p + 1, p + n + 1); for(int i = 1; i <= n; i ++) a[i] = p[i].second; for(int i = 1; i <= n; i ++){ f[i] = 1; for(int j = 1; j < i; j ++){ if(a[j] <= a[i]) f[i] = max(f[i],f[j] + 1); } } int res = 0; for(int i = 1; i <= n; i ++) res = max(res,f[i]); cout << res; return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:662 |
哥德巴赫曾猜测 (C语言代码)浏览:1015 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:600 |
printf基础练习2 (有点不明白)浏览:844 |
最小公倍数 (C语言代码)浏览:1029 |
关于float,double变量的几点说明浏览:1810 |
蚂蚁感冒 (C语言代码)浏览:773 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:669 |
简单的a+b (C语言代码)浏览:512 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:840 |