4286: §2 9 最大上升子序列和
[Creator : ]
Description
一个数的序列 $b_i$,当 $b_1<b_2<...<b_S$ 的时候,我们称这个序列是上升的。
对于给定的一个序列 $\{a_1,\ a_2,\ \cdots,\ a_N\}$,我们可以得到一些上升的子序列 $\{a_{i1},\ a_{i2},\ \cdots,\ a_{iK}\}$,这里 $1≤i_1<i_2<\cdots<i_K≤N$。
比如,对于序列 $\{1,\ 7,\ 3,\ 5,\ 9,\ 4,\ 8\}$,有它的一些上升子序列,如 $\{1,\ 7\}, \{3,\ 4,\ 8\}$ 等等。这些子序列中和最大为 $18$,为子序列 $\{1,\ 3,\ 5,\ 9\}$ 的和。
你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列 $\{100,\ 1,\ 2,\ 3\}$ 的最大上升子序列和为 $100$,而最长上升子序列为 $\{1,\ 2,\ 3\}$。
对于给定的一个序列 $\{a_1,\ a_2,\ \cdots,\ a_N\}$,我们可以得到一些上升的子序列 $\{a_{i1},\ a_{i2},\ \cdots,\ a_{iK}\}$,这里 $1≤i_1<i_2<\cdots<i_K≤N$。
比如,对于序列 $\{1,\ 7,\ 3,\ 5,\ 9,\ 4,\ 8\}$,有它的一些上升子序列,如 $\{1,\ 7\}, \{3,\ 4,\ 8\}$ 等等。这些子序列中和最大为 $18$,为子序列 $\{1,\ 3,\ 5,\ 9\}$ 的和。
你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列 $\{100,\ 1,\ 2,\ 3\}$ 的最大上升子序列和为 $100$,而最长上升子序列为 $\{1,\ 2,\ 3\}$。
Input
输入的第一行是序列的长度 $N(1≤N≤10^3)$。
第二行给出序列中的 $N$ 个整数,这些整数的取值范围都在 $0$ 到 $10000$(可能重复)。
第二行给出序列中的 $N$ 个整数,这些整数的取值范围都在 $0$ 到 $10000$(可能重复)。
Output
最大上升子序列和。
Sample 1 Input
7
1 7 3 5 9 4 8
Sample 1 Output
18
Sample 2 Input
4
100 1 2 3
Sample 2 Output
100