ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6674: 切木棍

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计Web Board

题目描述



有一根长度为L（L＜1000）的棍子，还有n（n＜50）个切割点的位置（按照从小到大排 列）。你的任务是在这些切割点的位置处把棍子切成n＋1部分，使得总切割费用最小。每次 切割的费用等于被切割的木棍长度。例如，L=10，切割点为2, 4, 7。如果按照2, 4, 7的顺序， 费用为10＋8＋6=24，如果按照4, 2, 7的顺序，费用为10＋4＋6=20。

输入格式

输入将由几个输入案例组成。每个测试用例的第一行将包含一个正数
数字l表示要切割的棍子的长度。你可以假设l<1000。下一行将
包含要进行的切割的数量n（n<50）。
下一行由n个正数ci（0<ci<l）组成，表示切割的位置
必须按照严格递增的顺序完成。
l=0的输入案例将表示输入的结束。

输出格式

您必须打印切割问题的最佳解决方案的成本，即最小成本
切割给定的棍子。按如下所示格式化输出
### 样例输入 #1

```
100
3
25 50 75
10
4
4 5 7 8
0
```

### 样例输出 #1

```
The minimum cutting is 200.
The minimum cutting is 22.
```

输入样例 复制 

100
3
25 50 75
10
4
4 5 7 8
0

输出样例 复制 

The minimum cutting is 200.
The minimum cutting is 22.

分类标签