2.7 KiB
2.7 KiB
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
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
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