codevs 3641 上帝选人
2024-08-28 12:21:24
3641 上帝选人
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商,数字大就代表其相应智商或情商高。现在你面前有N个人,这N个人的智商和情商均已知,请你选择出尽量多的人,要求选出的人中不存在任意两人i和j,i的智商大于j的智商但i的情商小于j的情商。
输入描述 Input Description
第一行一个正整数N,表示人的数量。 第二行至第N+1行,每行两个正整数,分别表示每个人的智商和情商。
输出描述 Output Description
仅一行,为最多选出的人的个数。
样例输入 Sample Input
3 100 100 120 90 110 80
样例输出 Sample Output
<nobr>2 </nobr>
数据范围及提示 Data Size & Hint
N<=1000;
/*基本思路:先把IQ按照降序排序,再根据这个顺序,跑一遍最长不上升子序列就可以了,无非就是把IQ的高低,作为了原来最长不上升子序列的数组下标而已*/
#include<iostream>
using namespace std;
#include<cstdio>
#define N 1001
int n;
#include<algorithm>
struct Peo{
int iq,love;
int line;
};
int dp[N][N];
Peo peo[N];
void input()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
scanf("%d%d",&peo[i].iq,&peo[i].love);
peo[i].line=;
}
}
int cmp(Peo a,Peo b)
{
return a.iq>b.iq;
}
void DP()
{
sort(peo+,peo+n+,cmp);
for(int i=n-;i>=;--i)
for(int j=i+;j<=n;++j)
if(peo[i].love>=peo[j].love&&peo[j].line+>peo[i].line)
peo[i].line=peo[j].line+;
int maxx=;
for(int i=;i<=n;++i)
if(peo[i].line>maxx)
maxx=peo[i].line;
cout<<maxx<<endl; }
int main()
{
input();
DP();
return ;
}
最新文章
- Javascript中数组方法和方法的扩展
- php缓存技术总结
- Java学习-043-获取文件在目录中的路径
- Linux/Unix shell 脚本监控磁盘可用空间
- Unity打包APK横屏时的注意事项
- WPF中Application.Current的使用
- Tenured 区并发垃圾回收器CMS介绍
- Paragraph 对象&#39;代表所选内容、范围或文档中的一个段落。Paragraph 对象是 Paragraphs 集合的一个成员。Paragraphs 集合包含所选内容、范围或文档中的所有段落。
- Maven中settings.xml的配置项说明精讲
- Nagios详解(基础、安装、配置文件解析及监控实例)
- Codeforces Round #543
- tmux使用中出现的问题和解决方式
- 网络安全实验室--SQL注入关
- JavaScript验证输入的字符是否包含表情
- 52-python 画图二维
- HoloLens开发手记 - 手势输入 Gesture input
- ExtJS4中设置tabpanel的tab高度问题
- 在pom.xml中添加Spring依赖
- 25-[jQuery]-事件
- JobDataMap 不能被序列化如何解决研究中
热门文章
- Part2-HttpClient官方教程-Chapter3-HTTP状态管理
- monkey测试===如何获取android app的Activity
- 访问dubbo没有权限,通过ip进行跳转服务器,并通过有权限服务器代理访问
- java的应用项目
- Spring,tk-mapper源码阅读
- docker基于本地模版导入创建镜像
- http-server:一个简单的零配置命令行的http服务器
- redis之(十)redis实现消息中间件的功能
- hdu 2044-2050 递推专题
- OpenStack 计算服务 Nova介绍和控制节点部署 (八)