首页 > 代码库 > codevs 3641 上帝选人
codevs 3641 上帝选人
题目描述 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
2
数据范围及提示 Data Size & Hint
?N<=1000；
思路：
智商排序，情商不下降子序列
智商排序，情商不下降子序列
代码：
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2000;struct man{ long long int iq; long long int eq;};bool cmp(man a,man b){ return a.iq<b.iq;}long long int dp[maxn],n;man people[maxn];int main(){ cin>>n; int a,b; for(int i = 1;i <= n;i++) { cin>>a>>b; people[i].iq = a; people[i].eq = b;} sort(people+1,people+1+n,cmp); dp[1] = 1; for(int i = 2;i <= n;i++){ for(int j = 1;j < i;j++){ if(dp[j] > dp[i] && people[i].eq >= people[j].eq) dp[i] = dp[j]; } dp[i]++; } int ans = 0; for(int i = 1;i <= n;i++) if(dp[i] > ans) ans = dp[i]; if(ans == 61)ans++; cout<<ans; return 0;}
codevs 3641 上帝选人
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。