2026-07-03：区别二进制字符串的小用度。用go言语鹰潭钢绞线厂家联系方式，有个只由 0 和 1 构成的二进制字符串 s，以及两个代价 encCost 和 flatCost。
把字符串 s 区别红些许个流通的片断（分段）。脱手把扫数这个词字符串视为个片断；允许不息陆续把某个片断拆成两个相邻的片断，直到得到终的区别案。
对恣意某个片断，设它的长度为 L，何况该片断中 1 的数目为 X（即敏锐元素的个数）：
拆分限定：
若是某个片断的长度是偶数，那么不错把它平均切成两个长度换取的流通片断。此时此次拆分产生的新总用度就是这两个子片断用度之和。
条件：在扫数繁荣限定的有区别中，求总用度的小可能值，并复返这个小总用度。
1
s 仅由 '0' 和 '1' 构成。
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，这是小可能的总用度。
题目来独力扣3864。
、代码举座施行分步拆解
要领1：预解决前缀和数组，快速求恣意区间1的总和
1. 字符串长度为n，创建长度n+1的前缀和数组sum，sum[0]=0。
2. 遍历字符串每位，sum[i+1] = sum[i] + 现时字符转数字（0或1）。
3. 作用：关于恣意左闭右开区间[l, r)，区间内1的总和X = sum[r] - sum[l]，O(1)查询恣意片断1的数目，避重迭遍历统计。
要领2：界说递归DFS函数 dfs(l, r)：求区间[l, r)片断的小总用度
函数输入l左规模、r右规模，代表原字符串从下标l到r-1的子串片断，复返该片断扫数法拆分案里的小用度，分4步施行：
分支1：现时片断全是0（X=0）
通过前缀和算出区间1总和X=sum[r]-sum[l]，若X=0：
该片断不行拆分化（论长度奇偶，用度固定为flatCost），平直复返flatCost。
分支2：先计划「不拆分」案的用度
现时片断含1（X>0），不作念任何拆分、平直保留扫数这个词片断的用度：
不拆分用度 = 片断长度 × 片断1总和 × encCost
把该值行为现时临时解res。
分支3：判断是否允许拆分，若允许则计划拆分后的用度并新小值
1. 计划现时片断长度len = r - l，独一len是偶数本事对半拆分；奇数平直跳过拆分逻辑。
2. 可拆分时，取中间分割点m=(l+r)/2，把片断平分操纵两段[l,m)、[m,r)。
3. 递归分别求出左段小用度dfs(l,m)、右段小用度dfs(m,r)，两段相加得到「拆分次」的总用度。
4. 对比临时解res和拆分总用度，取小的值新res。
分支4：复返现时片断的小用度res
论是否拆分，终复返该区间能得到的小用度。
要领3：进口调用与效果退换
1. 齐全字符串对应区间[0, n)，调用dfs(0, n)得到整型小总用度。
2. 将效果转为int64类型复返，止数值溢出。
要领4：主函数样例施行齐全历程（s=1010，n=4）
1. 预解决前缀和：sum数组为[0,1,1,2,2]
2. 调用dfs(0,4)：
• X=sum[4]-sum[0]=2≠0，片断长度4为偶数
• 不拆分用度：4×2×2=16，res开动=16
• 中点m=2，递归计划dfs(0,2) + dfs(2,4)
• 计划dfs(0,2)（子串"10"，L=2，X=1）
X=1≠0，不拆分用度2×1×2=4；长度2偶数，中点m=1
递归dfs(0,1) + dfs(1,2)
• dfs(0,1)（字符1，L=1奇数）：X=1鹰潭钢绞线厂家联系方式，钢绞线用度1×1×2=2，不可拆分，复返2
• dfs(1,2)（字符0，X=0）：平直复返flatCost=1
两段和=3，对比原值4，新res=3，复返3
• 计划dfs(2,4)（子串"10"），逻辑同上，复返3
• 两段总和3+3=6，对比开动res=16，新res=6
3. dfs(0,4)终复返6，输出效果6，和样例匹配。
二、算法存在的能迤逦（针对原题数据领域1e5）
现时已矣是纯递归，记念化缓存：
同个区间[l,r)会被屡次重迭递归计划；当字符串长度1e5时，递归度、重迭计划爆炸，会平直栈溢出+时，仅能解决小长度测试用例。
三、时辰复杂度 & 特等空间复杂度（分两种场景）
1. 现存记念化递归版块（代码原生已矣）
时辰复杂度
设字符串长度为n，每次偶数区间齐会分裂成两个等宗子区间，酿成满二叉拆分树：
拆分树节点总和为 O(n)，但记念缓存，多数区间重迭遍历，坏情况时辰复杂度为 O(2ⁿ)，指数，仅n≤20可运行，n=1e5不可用。
特等空间复杂度
1. 前缀和数组：长度n+1 → O(n)
2. 递归调用栈：每次对半拆分，栈大度 log₂n
总特等空间：O(n)（前缀和数组为主项）
2. 化后加多记念化DP（适配题目n≤1e5的轨范解法，补充参考）
若加多记念化哈希/区间DP缓存每个dfs(l,r)效果，每个唯区间仅计划次：
时辰复杂度
扫数法拆分区间总和为O(n)，每个区间O(1)计划，举座 O(n)
特等空间复杂度
前缀和数组O(n) + DP记念缓存O(n) + 递归栈O(logn)，总空间仍为 O(n)
Go齐全代码如下：
package main
import (
"fmt"
)
func minCost(s string, encCost, flatCost int)int64 {
n := len(s)
sum := make([]int, n+1)
for i, ch := range s {
sum[i+1] = sum[i] + int(ch-'0')
}鹰潭钢绞线厂家联系方式
// 计划子串 [l, r) 的小用度，凝视区间是左闭右开，便计划
var dfs func(int, int)int
dfs = func(l, r int)int {
x := sum[r] - sum[l]
if x == 0 {
return flatCost
}
// 不拆分
res := (r - l) * x * encCost
// 拆分
if (r-l)2 == 0 {
m := (l + r) / 2
res = min(res, dfs(l, m)+dfs(m, r))
}
return res
}
returnint64(dfs(0, n))
}
func main {
s := "1010"
encCost := 2
flatCost := 1
result := minCost(s, encCost, flatCost)
fmt.Println(result)
}
Python齐全代码如下：
# -*-coding:utf-8-*-
def minCost(s: str, encCost: int, flatCost: int) -> int:
n = len(s)
# 前缀和，纪录 '1' 的个数
prefix_sum = [0] * (n + 1)
for i, ch in enumerate(s):
prefix_sum[i + 1] = prefix_sum[i] + int(ch)
# 记念化搜索，避重迭计划
memo = {}
def dfs(l: int, r: int) -> int:
# 子串为 [l, r)，左闭右开
if (l, r) in memo:
return memo[(l, r)]
ones = prefix_sum[r] - prefix_sum[l]
zeros = (r - l) - ones
# 全是 0，平直压平
if ones == 0:
memo[(l, r)] = flatCost
return flatCost
# 不拆分：按位编码
res = (r - l) * ones * encCost
# 若是长度是偶数，尝试拆分
if (r - l) 2 == 0:
mid = (l + r) // 2
res = min(res, dfs(l, mid) + dfs(mid, r))
memo[(l, r)] = res
return res
return dfs(0, n)
def main:
s = "1010"
encCost = 2
flatCost = 1
result = minCost(s, encCost, flatCost)
print(result)
if __name__ == "__main__":
main
C++齐全代码如下：
#include
#include
#include
#include
#include
#include
using namespace std;
long long minCost(string s, int encCost, int flatCost) {
int n = s.length;
vector prefix_sum(n + 1, 0);
// 构建前缀和
for (int i = 0; i
prefix_sum[i + 1] = prefix_sum[i] + (s[i] - '0');
}
// 记念化搜索，使用字符串行为键存储景色
unordered_map memo;
// DFS函数
function dfs = [&](int l, int r) -> int {
// 生成景色键
string key = to_string(l) + "," + to_string(r);
if (memo.find(key) != memo.end) {
return memo[key];
}
int ones = prefix_sum[r] - prefix_sum[l];
// 全是0，平直压平
if (ones == 0) {
memo[key] = flatCost;
return flatCost;
}
// 不拆分：按位编码
int res = (r - l) * ones * encCost;
// 若是长度是偶数，尝试拆分
if ((r - l) 2 == 0) {
int mid = (l + r) / 2;
res = min(res, dfs(l, mid) + dfs(mid, r));
}
memo[key] = res;
return res;
};
return (long long)dfs(0, n);
}
int main {
string s = "1010";
int encCost = 2;
int flatCost = 1;
long long result = minCost(s, encCost, flatCost);
cout
return0;
}
咱们深信东说念主工智能为开阔东说念主提供了种“增强器用”，并奋勉于于共享全位的AI学问。在这里，您不错找到新的AI科普著作、器用评测、升迁率的秘密以及行业知悉。
迎接体恤“福大大架构师逐日题”，发音问可得到口试贵寓，让AI助力您的将来发展。天津市瑞通预应力钢绞线有限公司相关词条:离心玻璃棉 塑料挤出机 钢绞线厂家 铝皮保温 pvc管道管件胶
1.本网站以及本平台支持关于《新广告法》实施的“极限词“用语属“违词”的规定，并在网站的各个栏目、产品主图、详情页等描述中规避“违禁词”。
2.本店欢迎所有用户指出有“违禁词”“广告法”出现的地方，并积极配合修改。
3.凡用户访问本网页，均表示默认详情页的描述，不支持任何以极限化“违禁词”“广告法”为借口理由投诉违反《新广告法》鹰潭钢绞线厂家联系方式，以此来变相勒索商家索要赔偿的违法恶意行为。