题解 | 切割 01 串 2.0

#include<bits/stdc++.h>  // 包含所有常用标准库，竞赛中常用
using namespace std;

// 定义常量，数组最大长度
const int N=600;

// 全局变量声明
int n,L,R;          // n:字符串长度 L/R:分割后0和1数量差的上下限
string s;           // 输入的01字符串
int dp[N][N];       // dp[i][j]表示区间[i,j]能分割出的最大段数
int sum_zero[N],sum_one[N];  // 前缀和数组，sum_zero[i]表示前i个字符中0的数量，sum_one同理

// 核心动态规划求解函数
void solve(){
    // 枚举区间长度，从2开始（长度为1的区间无法分割）
    for(int len=2;len<=n;len++){
        // 枚举区间起点i，保证终点j不越界
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;  // 计算区间终点j
            // 枚举分割点k，将区间[i,j]拆分为[i,k]和[k+1,j]
            for(int k=i;k<j;k++){
                // 计算[i,k]区间内0的数量
                int pos1=sum_zero[k]-sum_zero[i-1];
                // 计算[k+1,j]区间内1的数量
                int pos2=sum_one[j]-sum_one[k];
                // 计算0和1数量的绝对差值
                int tp=abs(pos1-pos2);
                // 如果差值在[L,R]范围内，满足分割条件
                if(tp>=L&&tp<=R){
                    // 更新dp[i][j]为当前最大值
                    // 分割后段数 = 左区间段数 + 右区间段数 + 1（本次分割）
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+1);
                }
            }
        }
    }
    // 输出整个字符串[1,n]能分割出的最大段数
    cout<<dp[1][n]<<endl;
    return;
}

// 预处理前缀和数组
void pre(){
    // 从1开始遍历（方便前缀和计算，避免处理0边界）
    for(int i=1;i<=n;i++){
        // 继承前一个位置的前缀和
        sum_zero[i]=sum_zero[i-1],sum_one[i]=sum_one[i-1];
        // 字符串s是0下标，判断当前字符是0还是1，更新对应前缀和
        if(s[i-1]=='0') sum_zero[i]++;
        else sum_one[i]++;
    }
    return;
}

int main(){
    // 加速cin/cout输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 输入：字符串长度n，差值下限L，差值上限R
    cin>>n>>L>>R;
    // 输入01字符串
    cin>>s;
    
    // 预处理前缀和
    pre();
    
    // 动态规划求解
    solve();
    
    return 0;
}