钢条切割

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file cutrod.in Output file cutrod.out

【题目描述】


 Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案假定我们知道Serling公司出售一段长度为i英寸的钢条的价格为pi(i=1,2,…,n,单位为美元)。钢条的长度均为整英寸。

 钢条切割问题是这样的:给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,...,n),求切割钢条方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条的价格pn足够大,最优解可能就是完全不需要切割。


【输入格式】


有两行,第一行一个整数n            

第二行有n个整数,中间用一个空格隔开,第i个数表示长度为i的钢条的价值。

           


【输出格式】


第一行的整数表示最优值

第二行的若干整数表示取得最优值的方案,如果方案有多种,输出长钢条多的方案,输出时将方案按钢条长度从大到小排序。                                                            

           


【样例】

输入输出样例1:

cutrod.in

10 1 5 8 9 10 17 17 20 24 30

cutrod.out 30(最优价值)                   10(最优方案是不截断钢条,价值最大)

输入输出样例2:

cutrod.in

10 1 2 3 4 5 6 7 8 9 10

cutrod.out

10(最优价值)                   10(最优方案有截成2段2+8、1+9、...或截成3段2+3+5、1+3+6、...等多种方案,取钢条长度最长的方案。)

           

【提示】


数据规模:            

对于 30%的数据,0<n<=30;            

对于 100%的数据,0<n<=2000;