11419: 钢条切割问题（rod cutting problem）
[Creator : ]
Description
给定一段长度为 $n$ 英寸的钢条和一个价格表$p_i\ (i=1,2,...,n)$，求切割钢条方案，使得销售收益 $R_n$ 最大。
Input
第一行包括一个整数 $n\ (1 \leq n \leq 2\times 10^5)$。
第二行包括 $n$ 个非负整数，第 $i$ 个整数 $p_i\ (0 \leq p_i \leq 2\times 10^5)$ 表示第 $i$ 段钢条的价格。
第二行包括 $n$ 个非负整数，第 $i$ 个整数 $p_i\ (0 \leq p_i \leq 2\times 10^5)$ 表示第 $i$ 段钢条的价格。
Output
一行一个整数，表示答案。
Sample 1 Input
8
1 5 8 9 10 17 17 20
Sample 1 Output
22
将钢条切割成为 $2$ 段，即长度为 $2,6$，这样价值最大。
长度为 $2$ 的价值是 $5$
长度为 $6$ 的价值是 $17$
$17+5=22$。
Sample 2 Input
6
3 5 8 9 10 17
Sample 2 Output
18
切割成为长度为 $1$，这样价值最大。
$3\times 6=18$
Sample 3 Input
1
3
Sample 3 Output
3
4
1 20 33 36
40
Sample 4 Input
10
1 5 8 9 10 17 17 20 24 30
Sample 4 Output
30