切木棍 Cutting Sticks
题意翻译
翻译
有一根长度为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。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944
[PDF](https://uva.onlinejudge.org/external/100/p10003.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10003/958525065661f78575790c5f6aa2ffbee907fc0b.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10003/e46a5b9b0f145857448142f8f46dfaa75e9f6e02.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10003/c84a21fce404c85a1c20be6e70d4c5e2aac71537.png)
输入输出样例
输入样例 #1
100
3
25 50 75
10
4
4 5 7 8
0
输出样例 #1
The minimum cutting is 200.
The minimum cutting is 22.