4188: 钢条切割问题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 4 Solved: 4
[Status] [Submit] [Creator:]
Description
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。下图给出了一个价格表的样例。
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
Input
第一行 一个整数n
第二行 每个长度对应的价格，用空格分隔
第二行 每个长度对应的价格，用空格分隔
Output
一个整数，返回最大的价值
Sample Input Copy
10
1 5 8 9 10 17 17 20 24 3
Sample Output Copy
27