OI题库

【题目描述】

 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;