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