``` markdown
1（必做） 最优二分检索树
Score 100
给定标识符集 (a 
1
​
 ,a 
2
​
 ,…a 
n
​
 )，这些字符的下标从1开始按自然序编号，p 
i
​
  是对 a 
i
​
  成功检索的概率, q 
i
​
  是不成功检索的概率, 且 ∑ 
i=1
n
​
 p 
i
​
 +∑ 
i=0
n
​
 q 
i
​
 =1，问:它的最优二分检索树是怎样的？ 

输入格式:
第1行是 n ，表示字符个数。
第2行是这 n 个字符的成功检索概率p 
i
​
 ,0<p 
i
​
 <1 。
第3行是失败检索概率 q 
i
​
 ，0<q 
i
​
 <1 。
保证 ∑ 
i=1
n
​
 p 
i
​
 +∑ 
i=0
n
​
 q 
i
​
 =1 。

输出格式:
最优二分检索树先根遍历时得到的字符编号序列。若有多解，输出字典序最小的序列。

输入样例1:
4
0.1875 0.1875 0.0625 0.0625 
0.125 0.1875 0.0625 0.0625 0.0625 
输出样例1:
2 1 3 4 
输入样例2:
5
0.1524 0.1369 0.0179 0.0007 0.3081
0.1567 0.1022 0.0682 0.0476 0.0084 0.0009
输出样例2:
2 1 5 3 4 
数据范围
n≤100 

Code Size Limit
16 KB
Time Limit
1000 ms
Memory Limit
512 MB
Stack size limit
65536 KB
```


``` markdown
2 数列游戏
Score 100
一个数列有n个整数。每次从中取走一个最长的递增子数列，最少几次能取走全部的数。递增子数列中，相邻两项可以相等。

输入格式:
第1行，一个整数n，表示数列的项数，1≤n≤10000。

第2行，n个整数Ai，用空格分隔，Ai表示数列中第i项，1≤Ai≤1000000，1≤i≤n。

输出格式:
第1行，一个整数，表示第一次取走的最长子数列的项数。

第2行，n个整数，用空格分隔，表示第一次取走的最长子序列。如果有多种选择，输出最靠左的一组。

第3行，一个整数，表示所求最少次数。

输入样例:
在这里给出一组输入。例如：

8
10 9 2 5 3 7 101 18

输出样例:
在这里给出相应的输出。例如：

4
2 5 7 101
4

```



``` markdown
3 演讲大厅安排
Score 100
有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。
我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使
演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。
请计算演讲大厅最大可能的使用时间。

输入格式:
 第一行为一个整数 N，N≤5000，表示申请的数目。

 以下 n 行每行包含两个整数 p，k，1 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。

输出格式:
一个整数，表示大厅最大可能的使用时间。

输入样例1:
5
0 3
2 6
5 7
1 5
5 9
输出样例1:
8
输入样例2:
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
输出样例2:
16

```