LIS补锅
zasdcn
2022-07-31 20:36:38
# dp
```cpp
int main(){
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
}
}
for(int i=1;i<=n;++i)ans=max(f[i],ans);
return 0;
}
```
# 贪心
```cpp
int main(){
for(int i=1;i<=n;++i){
if(a[i]>d[len])d[++len]=a[i];
else {
int j=lower_bound(d+1,d+1+len,a[i])-d;
d[j]=a[i];
}
}
return 0;
}
```
# 树状数组：
```cpp
struct BIT{
int c[N];
int lowbit(int x){return x&(-x);}
void modify(int i,int val){
while(i<=n){
c[i]=max(c[i],val);
i+=lowbit(i);
}
}
int query(int i){
int res=0;
while(i>0){
res=max(res,c[i]);
i-=lowbit(i);
}
return res;
}
}S;
struct node{
int id,w;
}a[N];
bool cmp(node a,node b){
if(a.w!=b.w)return a.w<b.w;
return a.id<b.id;
}
int main(){
n=read();
for(int i=1;i<=n;++i)a[i].w=read(),a[i].id=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i){
int maxn=S.query(a[i].id);
maxn++;
S.modify(a[i].id,maxn);
ans=max(ans,maxn);
}
printf("%d\n",ans);
return 0;
}
```
关于树状数组，其实学了cdq分治之后就显然了，额···其实就是优化dp