题解 | #切割成本#

切割成本

http://www.nowcoder.com/practice/5c5fa5bf2a9942fcb1a3844d715087b9

题意

长最大为 $1000000$ 的线段上，给n个点。

其中每选择一个点，线断根据这个点分成两段，代价为这个线段的长度

找一个点的序列，使得代价总和最小，求这个最小代价。

其中 $n < 300$

方法

递归分治（TLE）

以题目为例[2,5,10,18]

表示成图就是

--|---|-----|--------|--

任选一处分成两段后，子线段的分割方案对父线段的分割方案无影响。所以这个问题可以分治。

枚举所有点，每次选择一个点， $f (线段) = 线段长度 + m i n (f (选点左侧的线段) + f (选点右侧的线段))$

因此实现如下

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param monsterLength int整型 线段长度
# @param monsterPoint int整型一维数组 切割点位置
# @return int整型
#
class Solution:
    def attackMonster(self , monsterLength , monsterPoint ):
        monsterPoint.sort()
        if len(monsterPoint) == 0:
            return 0
        ans = 0x3f3f3f3f
        for i in range(len(monsterPoint)):
            ans = min(ans,
                      monsterLength 
                      + self.attackMonster(monsterPoint[i], monsterPoint[:i])
                      +self.attackMonster(monsterLength-monsterPoint[i],[v-monsterPoint[i] for v in monsterPoint[i+1:]]))
        return ans

复杂度分析

时间复杂度: 因为我们采取递归的方式，从上向下以此尝试了所有方案，所以时间复杂度为 $O (n!)$

空间复杂度: 空间复杂度与递归深度相关，所以复杂度为 $O (n)$

DFS+记忆化

由题目的样例1，有4种分法

2	3	5	8	2
左	右	右	右	右
左	左	右	右	右
左	左	左	右	右
左	左	左	左	右

对每种分法的子线段[2],[2,3],[2,3,5],[2,3,5,8],[3,5,8,2],[5,8,2],[8,2],[2], 仍然是一个连续数组的分割，因此实际上所有的分割，都属于 $[节点左, 节点右]$

因此状态数为 $O (节点^{2})$

因此使用记忆化来优化重复计算。

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param monsterLength int整型 线段长度
# @param monsterPoint int整型一维数组 切割点位置
# @return int整型
#
class Solution:
    mem = []
    # sti 节点 + 0~sz-1 的节点是可切割的
    # 线段 [sti-1...sti+sz]
    def dfs(self, p, sti, sz):
        if sz == 0:
            return 0
        if self.mem[sti][sz] != 0x3f3f3f3f: # 记忆化
            return self.mem[sti][sz]
        ans = 0x3f3f3f3f
        for i in range(sz):
            ans = min(ans,
                      p[sti+sz] - p[sti-1] 
                      + self.dfs(p, sti, i) # 左
                      + self.dfs(p, sti+i+1, sz - i -1) # 右
                     )
        self.mem[sti][sz] = ans
        return ans
        
    def attackMonster(self , monsterLength , monsterPoint ):
        monsterPoint.sort()
        self.mem = [[0x3f3f3f3f for i in range(len(monsterPoint)+2)] for j in range(len(monsterPoint)+2)]
        # 增加首位节点 方便计算
        return self.dfs([0]+monsterPoint+[monsterLength],1,len(monsterPoint))