P4309 [TJOI2013]最长上升子序列 [vector+树状数组]

本文主要是介绍P4309 [TJOI2013]最长上升子序列 [vector+树状数组]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

考虑每新加进来一个数, 要么答案还是之前的, 要么这个数重新更新一个

发现数是按顺序插入的, 也就是说一个数无论放在哪里, 它后面的数对它都没有影响

于是我们可以用平衡树之类的东西先把原序列搞出来

然后按位置插入当前位置的值, 更新当前的DP值

可以树状数组维护, 然后惊讶地发现平衡树那一步可以用vector水

---

#include<bits/stdc++.h>
#define N 100050
using namespace std;
vector<int> v;
int n, ans[N], c[N];
void Add(int x,int val){ for(;x<=n;x+=x&-x) c[x] = max(c[x],val);}
int Ask(int x){int ans=0; for(;x;x-=x&-x) ans = max(ans,c[x]); return ans;}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x; scanf("%d",&x); v.insert(v.begin()+x, i);}for(int i=0;i<n;i++){int now = v[i]; ans[now] = Ask(now) + 1;Add(now, ans[now]);}for(int i=1;i<=n;i++){ans[i] = max(ans[i], ans[i-1]);printf("%d\n",ans[i]);} return 0;
}

 

这篇关于P4309 [TJOI2013]最长上升子序列 [vector+树状数组]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---