注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3173][Tjoi2013]最长上升子序列  

2015-01-29 11:14:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3173: [Tjoi2013]最长上升子序列

也就像我这样低智商的人还要提示并且还WA了一次……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int tree[N];
int n,pos[N],data[N],tf[N],f[N],ans;
void push(int x,int val){for(;x<=n;x+=x&-x)tree[x]+=val;}
int get(int x){int re=0;for(;x;x-=x&-x)re+=tree[x];return re;}
int find(int x){
int l = 1,r = n;
while(l<r){
int mid = (l+r)/2;
if(get(mid) >= x+1)r = mid;
else l = mid+1;
}
push(l,-1);return l;
}
int main(){
int i,j,a,b;
//freopen("in.txt","r",stdin);
n = scan();
for(i=1;i<=n;i++)pos[i]=scan(),push(i,1);
for(i=n;i;i--){
a = find(pos[i]);
data[a] = i;
tf[i] = 1e9;
}
//for(i=1;i<=n;i++) printf("%d ",data[i]);printf("\n");
for(i=1;i<=n;i++){
int l,r;
if(i==4)
i=4;
l = 0;r = ans;
while(l<r){
int mid = (l+r+1)/2;
if(tf[mid] < data[i])l=mid;
else r=mid-1;
}
f[data[i]] = l + 1;
if(l+1 > ans)ans = l+1;
if(data[i] < tf[l+1])tf[l+1]=data[i];
}
ans = 0;
for(i=1;i<=n;i++){
f[i] = max(f[i],ans);
ans = f[i];
printf("%d\n",f[i]);
}
return 0;
}

题解:
树状数组+乱搞
考虑暴力:每次插入一个数之后先更新到这个点的最长上升子序列,然后再更新这个数之后的所有数。
然后我就蛋疼了
看了一眼提示才意识到插入的数是递增的,然后每次插入就只要更新到这个点的答案。
如果我们知道最终的序列,在上面求最长上升子序列,那么对于一个点的答案f[i]有贡献的点一定在这个点之前被插入。
所以我们把所有f[i]按照这个点的权值排序每次输出max{f[1~i]}就行了。
现在就只剩下一个问题了:怎么还原出原序列。
一个比较明显的思路:正着用Splay模拟
但是感觉有点浪费。
倒序模拟一下过程,可以发现每次相当于找一个位置使得前面比它早插入的个数恰好=输入的数。
所以每次二分位置用树状数组维护一下前缀和就好了,虽然是log^2但是由于常数小跑得很快
  评论这张
 
阅读(37)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017