发现自己dp学的非常不好 所以开始练习dp
（当然从最简单的开始啦）
为什么这道题是个紫题？？分明代码很简单（对于多数线段树树状数组的码量来看）
个人认为思路有点难想出来（我就是看了题解才会的）
步入正题
题目描述每次插入一个数k到xk位置（0<k<=n)
那么就是一个动态的啦
插入一个数k到xk位置后
对于区间（1，xk）已经在之前求解过最长子序列
那么只用找出（1，xk）区间内lis的最大值+1就可以了
然后更新（kx，n）
用树状数组就可以实现啦
具体看代码
#include<bits/stdc++.h> using namespace std; int ans[1000001],n,tree[1000001]; vector<int> a; inline void updata(int x,int v){ while(x<=n){ tree[x]=max(tree[x],v); x+=x&-x; } } inline int query(int x){ int t=0; while(x){ t=max(t,tree[x]); x-=x&-x; } return t; } int main(){ cin>>n; for(int i=1,t;i<=n;i++){ scanf("%d",&t); a.insert(t+a.begin(),i); } for(int i=0,t;i<n;i++){ t=a[i]; updata(t,ans[t]=query(t)+1); } for(int i=1;i<=n;i++){ printf("%d\n",ans[i]=max(ans[i],ans[i-1])); } return 0; }
原文：https://www.cnblogs.com/duojiaming/p/11668111.html