目录
- T1. 最长上升子序列
- 思路分析
- T2. 神奇的口袋
- 思路分析
- T3. 滑雪
- 思路分析
- T4. 删除数字
T1. 最长上升子序列
一个数的序列 b i b_i bi,当 b 1 < b 2 < ⋯ < b S b_1 < b_2 < \dots < b_S b1<b2<⋯<bS 的时候,我们称这个序列是上升的。对于给定的一个序列 ( a 1 , a 2 , … , a N ) (a_1, a_2, \dots, a_N) (a1,a2,…,aN),我们可以得到一些上升的子序列 ( a i 1 , a i 2 , … , a i K ) (a_{i_1}, a_{i_2}, \dots, a_{i_K}) (ai1,ai2,…,aiK),这里 1 ≤ i 1 < i 2 < ⋯ < i K ≤ N 1 \le i_1 < i_2 < \dots < i_K \le N 1≤i1<i2<⋯<iK≤N。
比如,对于序列 ( 1 , 7 , 3 , 5 , 9 , 4 , 8 ) (1, 7, 3, 5, 9, 4, 8) (1,7,3,5,9,4,8),有它的一些上升子序列,如 ( 1 , 7 ) , ( 3 , 4 , 8 ) (1, 7),\ (3, 4, 8) (1,7), (3,4,8) 等等。这些子序列中最长的长度是 4 4 4,比如子序列 ( 1 , 3 , 5 , 8 ) (1, 3, 5, 8) (