切割成本

[编程题]切割成本

热度指数：1391 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。

示例1

输入

20,[2,5,10,18]

输出

说明

线段长为20，切割点为[2,5,10,18]。
第一种方案：
1.先切开第一个点，成本为2+18=20
2.切开第二个点，成本为3+15=18
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 18 + 15 + 10 = 63;
第二种方案：
1.先切开第一个点，成本为5+15=20
2.切开第二个点，成本为2+3=5
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 5 + 15 + 10 = 50;

备注:

切割点个数<300
x<1000000

算法知识视频讲解

Miss.Zhou

发表于 2020-02-07 13:02:05

很明显的一个区间dp首先把首尾两点加入读进去的数组中，排序就像正常的区间dp一样第一重循环：子区间长度第二重循环：子区间开头位置第三重循环：子区间的中间断的点时间复杂度![： ](https://www.nowcoder.com/equation?tex=N%5E%7B3%7D "图片标题") 展开全文

Maokt

发表于 2021-08-08 00:53:34

算法思想一：动态规划解题思路：可以用动态规划解决这个问题， 1、创建辅助数组dp，其中用表示之间（前闭后开）的切割点的最小成本，只要完善dp数组，最后就是要求的最小切割成本和。 2、通过在原切割点数组中加入首尾点，然后一起排序。然后从0结点开始找 i 到 j 的子区间展开全文

球球了给孩子一个offer吧

发表于 2021-08-04 21:49:06

题目描述：将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。示例输入：20,[2,5,10,18]返回值：45说明：线段长为20，切割点为[2,5,10,18]。第一种方案：1.先切开第一个点，成本为2+18=202.切开第二个点，成本展开全文