题意:
有n个人每人有一个力气值Si,美丽值Bi,满足Bi>Bj&&Si>Sj 或者 Bi<Bj&&Si<Sj 的人可以
一起参见晚会,问最多有多少人可以一起参见晚会。
思路: 我们根据S从小到大将所有人排序,然后看B最长的上升子序列的长度求出来即可!
在排序中优先对S排序,S相等的则对B进行由大到小的排序,why?
也就是对于S相同的,我们先选取B最大的值插入LIS中,因为比如 S1=1, B1 = 1
S1=1, B1 = 2, S1=1, B1 = 3, 如果不进行排序,直接按照求B中的lis,显然长度
为3,显然是不对的,因为相同的S中只能选择一个B出来!所以就要对S相同的B进行
降序排序! 这样就变成了一个裸lis!

 #include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 100005
using namespace std; struct node{
int x, y;
int p;
}; bool cmp(node a, node b){
if(a.x == b.x)
return a.y > b.y;
return a.x < b.x;
} bool myCmp(node a, node b){
return a.y <= b.y;//这里要写成 <=;因为upper_bound返回的是“元素值 >插入值”
//最后一个插入值的位置,元素值 == 插入值的时候,默认 元素值
// >插入值,但在该题中,相等的情况下不能算在lis中的!
} node a[N];
node c[N]; int pre[N], path[N]; int main(){
int n;
while(scanf("%d", &n) != EOF){
for(int i=; i<n; ++i)
scanf("%d%d", &a[i].x, &a[i].y), a[i].p = i+; sort(a, a+n, cmp);
c[] = a[];
pre[] = ;
path[] = ;
int len = ; for(int i=; i<n; ++i){
int k = upper_bound(c, c+len, a[i], myCmp) - c;
pre[i] = k ? path[k-] : ;//当前插入节点i的位置为k,它的前一个(k-1位置)元素的序号!
path[k] = i;//当前插入k位置的节点的序号
c[k] = a[i];
if(k+ > len) len = k+;
}
int tmp = path[len-];
printf("%d\n", len);
printf("%d", a[path[len-]].p);
for(int i=len-; i >= ; --i){
tmp = pre[tmp];
printf(" %d", a[tmp].p);
}
printf("\n"); }
return ;
}

最新文章

  1. android中的线程池学习笔记
  2. vi的使用规则
  3. Entity Framework的核心 – EDM(Entity Data Model) 一
  4. 对OCR文字识别软件的扫描选项怎么设置
  5. java.io.EOFException java.io.ObjectInputStream$PeekInputStream.readFully 错误
  6. 微信 ua
  7. vsftpd2.3.2安装、配置详解
  8. Survival(ZOJ 2297状压dp)
  9. oracle 表空间常用语句
  10. Android调用系统关机与重启功能
  11. 基于visual Studio2013解决C语言竞赛题之0522和为素
  12. 解决hexo神烦的DTraceProviderBindings MODULE_NOT_FOUND
  13. 在本地没有安装Oracle的情况下,使用plsql远程连接数据库
  14. 『片段』Win32 模式窗体 消息路由
  15. 一文看懂https如何保证数据传输的安全性的
  16. udt的java实现
  17. mysql 时间戳的使用!
  18. 微信小程序 windos server 2008 iis 7 tls1.0 升级 tls1.2
  19. AT&amp;T汇编格式
  20. View的工作原理(一) 总览View的工作流程

热门文章

  1. cached过高导致内存溢出 java head space
  2. JavaWeb学习总结(十七)——JSP中的九个内置对象
  3. jq滚动监听-导航滚动
  4. hive函数 -- split 字符串分割函数
  5. c#之第一课入门
  6. gridlaylout 简单布局
  7. android如何播放和录制音频
  8. 奇怪吸引子---Thomas
  9. 用thinkphp写的一个例子:抓取网站的内容并且保存到本地
  10. Android--ColorMatrix改变图片颜色