题解 | #切割 01 串 2.0#

1.分析

   本体就是一个简单的区间dp板子题加了一个判断

2.AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,L,R;
    cin>>n>>L>>R;
    string s;
    cin>>s;
    s = " "+s;//从1开始更符合习惯
    vector<int>p0(n+1);//前 i 个字符中 '0' 的个数（前缀和）
    vector<int>p1(n+1);//前 i 个字符中 '1' 的个数（前缀和）
    vector<vector<int>>dp(n+1,vector<int>(n+1,0));//把子串s的i至j部分按题目规则最多能分成的段数
    for(int i = 1;i<=n;++i)//预处理前缀和
    {
        if(s[i] == '0')
        {
            p0[i] = p0[i-1]+1;
            p1[i] = p1[i-1];
        }else if(s[i] == '1')
        {
            p0[i] = p0[i-1];
            p1[i] = p1[i-1]+1;
        }
    }
    for(int len = 2;len<=n;++len)//枚举区间的长度，len = 1时为0与初始化的dp值一致不用枚举了
    {
        for(int i = 1;i+len-1<=n;++i)//枚举区间左端点i
        {
            int j = i+len-1;//用i和len计算出对应的区间右端点的位置j
            for(int k = i;k<j;++k)//枚举所有可能的切点
            {
                int c0 = p0[k] - p0[i-1];//计算出题目要求的c0
                int c1 = p1[j] - p1[k];//计算出题目要求的c1
                if(abs(c0-c1)>=L&&abs(c0-c1)<=R)//根据题目要求判断
                {
                    dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+1);/*进入if语句说明满足s在区间i到j可以在k处切割一下
                    在加上更小的区间的最大切割次数结果就为dp[i][k]+dp[k+1][j]+1，
                    因为len是从小开始枚举，所以dp[i][k]与dp[k+1][j]均以计算过了
                    且表示其代表的区间的最大切割次数，
                    因此最后得到的dp[1][n]就为整的s的最大切割次数*/
                }
            }
        }
    }
    cout<<dp[1][n]<<'\n';//输出结果
    
    
}