T3864.划分二进制字符串的最小费用

线段树，区间dp，https://leetcode.cn/problems/minimum-cost-to-partition-a-binary-string/

给你一个二进制字符串 s 和两个整数 encCost 与 flatCost。

对于每个下标 i，s[i] = '1' 表示第 i 个元素是敏感的，而 s[i] = '0' 表示它不是敏感的。

该字符串必须被划分为分段。最初，整个字符串形成一个单一的分段。

对于一个长度为 L 且包含 X 个敏感元素的分段:

如果 X = 0，费用为 flatCost。
如果 X > 0，费用为 L * X * encCost。

如果一个分段具有 偶数长度，你可以将其拆分为两个长度相等的 连续分段，此次拆分的费用是所得分段的 费用之和。

返回一个整数，表示所有有效划分中的 最小可能总费用。

示例 1：

输入： s = "1010", encCost = 2, flatCost = 1

输出： 6

解释：

整个字符串 s = "1010" 长度为 4，包含 2 个敏感元素，费用为 4 * 2 * 2 = 16。
由于长度为偶数，它可以被拆分为 "10" 和 "10"。每个分段长度为 2 且包含 1 个敏感元素，因此每个分段的费用为 2 * 1 * 2 = 4，总计 8。
将两个分段继续拆分为四个单字符分段，得到 "1"、"0"、"1" 和 "0"。包含 "1" 的分段长度为 1 且恰好有一个敏感元素，费用为 1 * 1 * 2 = 2；而包含 "0" 的分段没有敏感元素，因此费用为 flatCost = 1。
因此总费用为 2 + 1 + 2 + 1 = 6，这是最小可能的总费用。

示例 2：

输入： s = "1010", encCost = 3, flatCost = 10

输出： 12

解释：

整个字符串 s = "1010" 长度为 4，包含 2 个敏感元素，费用为 4 * 2 * 3 = 24。
由于长度为偶数，它可以被拆分为两个分段 "10" 和 "10"。
每个分段长度为 2 且包含一个敏感元素，因此每个分段费用为 2 * 1 * 3 = 6，总计 12，这是最小可能的总费用。

示例 3：

输入： s = "00", encCost = 1, flatCost = 2

输出： 2

解释：

字符串 s = "00" 长度为 2 且不包含敏感元素，因此将其作为一个单一分段存储的费用为 flatCost = 2，这是最小可能的总费用。

提示：

1 <= s.length <= 10^5
s 仅由 '0' 和 '1' 组成。
1 <= encCost, flatCost <= 10^5

python

class Solution:
    def minCost(self, s: str, encCost: int, flatCost: int) -> int:
        n = len(s)

        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[i] + (s[i] == '1')

        def dfs(l, length):
            x = pre[l+length] - pre[l]

            if x == 0:
                cost = flatCost
            else:
                cost = length * x * encCost

            if length % 2 == 0:
                half = length // 2
                cost = min(cost, dfs(l, half) + dfs(l+half, half))

            return cost

        return dfs(0, n)

T3864.划分二进制字符串的最小费用 ​

T3864.划分二进制字符串的最小费用