题目描述

给定一个长度为 的 01 串 ，以及两个整数参数 和 。我们可以对任意一个长度大于等于2的子串进行“切割”操作。

一次合法的切割操作定义如下：

  1. 选择一个子串，将其分成两个非空的连续子串 （左）和 （右）。
  2. 记 中字符 '0' 的出现次数为 ， 中字符 '1' 的出现次数为 。
  3. 当且仅当 时，此次切割是合法的。

每次合法切割后产生的两个新子串，如果长度仍然大于等于2，可以被独立地继续进行切割。问题是，在最优策略下，最多可以执行多少次切割操作。

解题思路

这是一个典型的区间动态规划问题。问题的最优解包含其子问题的最优解（最优子结构），且子问题会被重复计算（重叠子问题），这完全符合动态规划的应用场景。

1. 状态定义

我们定义一个二维DP数组， 表示对字符串 的子串 （从索引 到 ）进行操作，能获得的最大切割次数。我们的最终目标是求解 。

2. 状态转移

为了计算 ，我们需要考虑所有可能的“第一刀”切在哪里。假设我们在位置 （其中 ）进行切割，将子串 分成两部分：左子串 和右子串 。

  • 合法性检查:

    • 首先，我们需要判断这次切割是否合法。我们需要计算 中 '0' 的数量 () 和 中 '1' 的数量 ()。
    • 然后，判断它们的差的绝对值是否在 区间内，即 。

  • 转移方程:

    • 如果这次在 处的切割是合法的，那么我们能获得的总切割次数是： (当前这次切割) (左子串的最优切割次数) (右子串的最优切割次数)。
    • 我们需要遍历所有可能的切割点 ，在所有合法的切割中，取一个能使总次数最大化的值。
    • 因此，状态转移方程为： ，其中切割点 必须满足合法性条件。
    • 如果对于所有的 都不存在合法的切割，那么 。

3. 优化：前缀和

在状态转移中，我们需要频繁计算子串中 '0' 和 '1' 的数量。如果每次都遍历子串来计数，时间复杂度会很高。我们可以使用前缀和来进行优化。

  • 创建两个前缀和数组 prefix_zeros 和 prefix_ones。
  • 存储原串 中 '0' 的数量。
  • 存储原串 中 '1' 的数量。
  • 这样，计算任意子串 中 '0' 或 '1' 的数量就可以在 时间内完成。

4. 实现细节

我们按照子串的长度，从小到大进行计算。

  • 遍历顺序:

    1. 外层循环遍历子串长度 len，从 2 到 。
    2. 中层循环遍历子串的起始位置 i，从 0 到 。
    3. 由此确定子串的结束位置 j = i + len - 1。
    4. 内层循环遍历切割点 k，从 i 到 j-1。

  • 基本情况: 。长度为 1 的子串无法切割，所有 值可以初始化为 0。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, l, r;
    cin >> n >> l >> r;
    string s;
    cin >> s;

    // 计算前缀和
    vector<int> prefix_zeros(n + 1, 0);
    vector<int> prefix_ones(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_zeros[i + 1] = prefix_zeros[i] + (s[i] == '0');
        prefix_ones[i + 1] = prefix_ones[i] + (s[i] == '1');
    }

    vector<vector<int>> dp(n, vector<int>(n, 0));

    // len 表示子串长度
    for (int len = 2; len <= n; ++len) {
        // i 表示子串起始位置
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1; // j 表示子串结束位置
            // k 表示切割点
            for (int k = i; k < j; ++k) {
                // 左子串 S[i..k], 右子串 S[k+1..j]
                int c0 = prefix_zeros[k + 1] - prefix_zeros[i];
                int c1 = prefix_ones[j + 1] - prefix_ones[k + 1];
                int diff = abs(c0 - c1);

                // 判断切割是否合法
                if (diff >= l && diff <= r) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int r = sc.nextInt();
        String s = sc.next();

        // 计算前缀和
        int[] prefixZeros = new int[n + 1];
        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixZeros[i + 1] = prefixZeros[i] + (s.charAt(i) == '0' ? 1 : 0);
            prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) == '1' ? 1 : 0);
        }

        int[][] dp = new int[n][n];

        // len 表示子串长度
        for (int len = 2; len <= n; len++) {
            // i 表示子串起始位置
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1; // j 表示子串结束位置
                // k 表示切割点
                for (int k = i; k < j; k++) {
                    // 左子串 S[i..k], 右子串 S[k+1..j]
                    int c0 = prefixZeros[k + 1] - prefixZeros[i];
                    int c1 = prefixOnes[j + 1] - prefixOnes[k + 1];
                    int diff = Math.abs(c0 - c1);

                    // 判断切割是否合法
                    if (diff >= l && diff <= r) {
                        dp[i][j] = Math.max(dp[i][j], 1 + dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        System.out.println(dp[0][n - 1]);
    }
}

import sys

def main():
    n, l, r = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()

    # 计算前缀和
    prefix_zeros = [0] * (n + 1)
    prefix_ones = [0] * (n + 1)
    for i in range(n):
        prefix_zeros[i + 1] = prefix_zeros[i] + (1 if s[i] == '0' else 0)
        prefix_ones[i + 1] = prefix_ones[i] + (1 if s[i] == '1' else 0)

    dp = [[0] * n for _ in range(n)]

    # len 表示子串长度
    for length in range(2, n + 1):
        # i 表示子串起始位置
        for i in range(n - length + 1):
            j = i + length - 1 # j 表示子串结束位置
            # k 表示切割点
            for k in range(i, j):
                # 左子串 S[i..k], 右子串 S[k+1..j]
                c0 = prefix_zeros[k + 1] - prefix_zeros[i]
                c1 = prefix_ones[j + 1] - prefix_ones[k + 1]
                diff = abs(c0 - c1)

                # 判断切割是否合法
                if l <= diff <= r:
                    dp[i][j] = max(dp[i][j], 1 + dp[i][k] + dp[k + 1][j])

    print(dp[0][n - 1])

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 区间动态规划 (Interval DP)
  • 时间复杂度: 。我们有三层嵌套循环：子串长度 len ()，子串起始位置 i ()，以及切割点 k ()。前缀和的计算是 ，可以忽略不计。
  • 空间复杂度: 。主要开销是 的 DP 表。前缀和数组需要 的空间。