Problem 3173. -- [Tjoi2013]最长上升子序列 -- 衡阳八中OJ离线版-2014-11-04

F.A.Qs	Home	ProblemSet	Status	Ranklist	Contest	Login	Register	捐赠本站

Notice:开心刷题：）

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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 453 Solved: 249
[Submit][Status]

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

3
0 0 2

1
1
2

X0等于0 ，我们将1插入到位置0得到序列{1}

X1等于0 ，我们将1插入到位置0得到序列{2，1}

X2等于2 ，我们将1插入到位置0得到序列{2，1，3}

数据范围

30%的数据 n<=1000

100%的数据 n<=100000