POJ 1631 nlogn求LIS
2024-08-27 23:33:14
方法一: 二分
我们可以知道 最长上升子序列的 最后一个数的值是随序列的长度而递增的 (呃呃呃 意会意会)
然后我们就可以二分找值了(并更新)
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,cases,a[100050],f[100050],vis[100050];
int search(int x){
int l=0,r=n,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(vis[mid]<=x)l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
int main()
{
scanf("%d",&cases);
while(cases--){
memset(f,0,sizeof(f));
memset(vis,0x3f,sizeof(vis)),vis[0]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
f[i]=search(a[i])+1;
vis[f[i]]=min(vis[f[i]],a[i]);
}
for(int i=1;i<n;i++)f[n]=max(f[n],f[i]);
printf("%d\n",f[n]);
}
}
方法二:
线段树 (按照权值建) 查询前一段中的最大值。。并插入当前的值,,
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,cases,a[100050],f[100050],xx,tree[666666];
void insert(int l,int r,int pos){
if(l==r){tree[pos]=f[xx];return;}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<a[xx])insert(mid+1,r,rson);
else insert(l,mid,lson);
tree[pos]=max(tree[lson],tree[rson]);
}
int query(int l,int r,int pos){
if(r<=a[xx])return tree[pos];
int mid=(l+r)>>1;
if(mid<a[xx])return max(query(l,mid,pos<<1),query(mid+1,r,pos<<1|1));
else return query(l,mid,pos<<1);
}
int main(){
scanf("%d",&cases);
while(cases--){
memset(tree,0,sizeof(tree));
memset(f,0,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(xx=1;xx<=n;xx++){
f[xx]=query(1,n,1)+1;
insert(1,n,1);
}
for(int i=1;i<n;i++)f[n]=max(f[n],f[i]);
printf("%d\n",f[n]);
}
}
最新文章
- ereg/eregi报错处理办法
- 帝国备份王(Empirebak)万能cookie及拿shell
- 监控 Linux Unix Solaris AIX, swap page in / swap page out
- c#调用cmd的ping命令
- Objective-C命名编写规范
- 批量翻转PNG图片
- ViewData与ViewBag比较
- 每个线程分配一个stack,每个进程分配一个heap;heap没有结构,因此寻址慢(转)
- mac版VMware fusion
- MySQL 导出命令
- MyBatis 3 User Guide Simplified Chinese.pdf
- java中,字符串和集合判断是否为空
- 第四篇 - 爬取前程无忧python相关工作
- Linux下java开发环境配置总结
- 干货,比较全面的c#.net公共帮助类(Common.Utility)
- Python的容器、生成器、迭代器、可迭代对象的家谱
- 探索Java8:(二)Function接口的使用
- 最短路径-Dijkstra算法(转载)
- (剑指Offer)面试题60:把二叉树打印成多行
- If the parts of an organization (e.g., teams, departments, or subdivisions) do not closely reflect the essential parts of the product, or if the relationship between organizations do not reflect the r
热门文章
- poj3101--Astronomy(分数的最小公倍数)
- 1067. Sort with Swap(0,*) (25)【贪心】——PAT (Advanced Level) Practise
- 编写shell脚本获取本机的网络地址。&;#160; 比方:本机的ip地址是:192.168.100.2/255.255.255.0,那么它的网络地址是&;#160;192.168.100.1/255.255.255.
- ServiceStack.Redis之IRedisClient<;第三篇>;【转】
- 接口、索引器、Foreach的本质(学习笔记)
- 编程语言与Python学习(一)
- (转)PHP(其他语言类似)编码的规范性
- django steps EASY WAY
- <;Three.js>;(第三节)全景漫游
- STM8S103之GPIO