2338: 最长上升子序列
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:16
解决:5
题目描述
对于一个1..N 的排列{Pi},定义Fi为以第i个数结尾的最长上升子序列的长度,那么Fi可以用下述转移方程求出F0=0,Fi = Max{Fj} + 1 (i ∈ [1,N],j<i,Pj<Pi)
现在,给你N 和{Fi},要你还原出排列{Pi}。
输入
第一行T 表示数据组数,每组数据按如下格式:
N
F1 F2 F3 ⋯⋯ Fn (1<=Fi<=N)
输出
T 行,每组数据一行。
对于每组数据,如果无解则输出:No
否则按如下格式输出排列{Pi}:P1 P2 P3 ⋯⋯ Pn
(有多组解时请输出字典序最小的那组)
样例输入 复制
2
5
1 2 2 3 1
4
1 3 2 3
样例输出 复制
2 4 3 5 1
No
提示
【数据规模】
40%数据满足 T<=10 1<=N<=15
100%数据满足 1<=N<=100000