题解

问题分析

我们需要将给定的 0/1 序列划分为不超过 $k$ 个连续的段，每段内所有字符相同，使得需要改变的字符数量最少。

关键观察

1. 代价计算：对于区间 $[l, r]$，如果统一为一种颜色，最小代价为：

   $$\text{cost}(l, r) = \min(\text{count}_0, \text{count}_1) $$

   即选择该区间内出现次数较少的颜色进行改变。

2. 动态规划状态：

   • $dp[i][j]$：前 $i$ 个字符划分为 $j$ 个段的最小代价
   • 最终答案：$\min\limits_{1 \le j \le k} dp[n][j]$

基础动态规划

状态转移方程

$$dp[i][j] = \min\limits_{0 \le l < i} \{ dp[l][j-1] + \text{cost}(l+1, i) \} $$

其中 $\text{cost}(l, r)$ 可以通过前缀和 $O(1)$ 计算。

算法步骤

1. 预处理前缀和：

   prefix0[i] = 前i个字符中'0'的数量
   prefix1[i] = 前i个字符中'1'的数量
   

2. 初始化：

   • $dp[0][0] = 0$
   • 其他状态初始化为无穷大

3. 状态转移：

   for i in range(1, n+1):
       for j in range(1, min(k, i)+1):
           for l in range(0, i):
               zeros = prefix0[i] - prefix0[l]
               ones = prefix1[i] - prefix1[l]
               cost = min(zeros, ones)
               dp[i][j] = min(dp[i][j], dp[l][j-1] + cost)
   

4. 回溯构造解： 从 $dp[n][j]$ 回溯，记录每个分段的位置和选择的颜色。

复杂度分析

• 时间复杂度：$O(n^2k)$
• 空间复杂度：$O(nk)$

对于 $n \leq 10$ 的小数据可行。

优化方法

优化1：决策单调性（适用于中等数据）

观察到对于固定的 $j$，决策点 $l^*(i)$ 是单调的，可以使用分治优化：

def solve_dc(j, l, r, opt_l, opt_r):
    if l > r: return
    mid = (l + r) // 2
    best = inf, -1
    for t in range(opt_l, min(opt_r, mid)+1):
        cost = min(prefix0[mid]-prefix0[t], prefix1[mid]-prefix1[t])
        current = dp[t][j-1] + cost
        if current < best[0]:
            best = current, t
    dp[mid][j] = best[0]
    solve_dc(j, l, mid-1, opt_l, best[1])
    solve_dc(j, mid+1, r, best[1], opt_r)

复杂度：$O(nk \log n)$

优化2：凸性优化（适用于大数据）

关键观察：代价函数 $\text{cost}(l, r)$ 具有凸性，可以使用凸包技巧（CHT）优化。

将转移方程重写为：

$$dp[i][j] = \min\limits_{0 \le l < i} \{ dp[l][j-1] + \min(prefix1[i]-prefix1[l], prefix0[i]-prefix0[l]) \} $$

由于 $prefix0[i] + prefix1[i] = i$，可以进一步简化。

样例验证

样例1

n=9, k=3, s="000111000"

最优解：000111000（不需要改变任何像素）

• 分为3段：000、111、000
• 代价：0

样例2

n=10, k=3, s="0111011010"

最优解：0111111000

• 分为3段：0111111、000（实际输出为 0111111000）
• 代价分析：需要具体计算

实现细节

1. 内存优化：使用滚动数组，只存储当前层和上一层的DP值
2. 边界处理：注意前缀和数组的边界索引
3. 解的重构：在DP过程中记录决策点，最后回溯构造解

完整算法（决策单调性优化）

def solve_photo(n, k, s):
    # 预处理前缀和
    prefix0 = [0] * (n+1)
    prefix1 = [0] * (n+1)
    for i in range(1, n+1):
        prefix0[i] = prefix0[i-1] + (1 if s[i-1] == '0' else 0)
        prefix1[i] = prefix1[i-1] + (1 if s[i-1] == '1' else 0)
    
    # DP数组（使用滚动数组）
    dp_prev = [0] * (n+1)
    dp_curr = [inf] * (n+1)
    decision = [[-1] * (n+1) for _ in range(k+1)]
    
    # 初始化
    for i in range(1, n+1):
        dp_prev[i] = min(prefix0[i], prefix1[i])
    
    # 分层DP
    for j in range(2, k+1):
        # 使用分治优化求解第j层
        solve_layer(j, n, dp_prev, dp_curr, prefix0, prefix1, decision)
        dp_prev, dp_curr = dp_curr, dp_prev
    
    # 回溯构造解
    return reconstruct(n, k, s, decision)

总结

本题的核心在于：

1. 将问题建模为带段数限制的序列分割问题
2. 使用动态规划求解最小代价
3. 利用决策单调性等优化技巧处理大规模数据
4. 通过回溯构造最优解

对于不同规模的数据，选择合适的优化策略是关键。