切割 01 串 2.0【牛客tracker 每日一题】

切割 01 串 2.0时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个长度为n nn的01 0101串s ss。一次切割操作如下选择一个长度≥ 2 ≥2≥2的子串将其分成两个非空连续子串a aa左和b bb右记a aa中字符0 00的出现次数为C 0 C_0C0​​b bb中字符1 11的出现次数为C 1 C_1C1​仅当L ≦ ∣ C 0 − C 1 ∣ ≦ R L≦∣C_0−C_1∣≦RL≦∣C0​−C1​∣≦R时此次切割被视为合法。每次合法切割产生的两个子串都可以继续被独立切割若长度≥ 2 ≥2≥2且满足切割条件。问在最优策略下最多可以执行多少次切割输入描述第一行输入三个整数n , L , R ( 1 ≦ n ≦ 500 , 0 ≦ L ≦ R ≦ 500 ) n,L,R (1≦n≦500, 0≦L≦R≦500)n,L,R(1≦n≦500,0≦L≦R≦500)——字符串长度与参数限制。第二行输入一个长度为n nn的01 0101串s ss。输出描述输出一个整数表示最多能执行的切割次数。示例1输入6 2 3 011011输出3说明其中一种切割次数最多的切法如下第一次切割可以切0 ∣ 11011 0 ∣ 110110∣11011然后选择11011 1101111011这个串继续做切割。第二次切割可以切1 ∣ 1011 1 ∣ 10111∣1011然后选择1011 10111011这个串继续做切割。第三次切割可以切1 ∣ 011 1 ∣ 0111∣011。解题思路本题是区间动态规划的经典应用题利用切割问题的最优子结构性质通过拆分区间逐步求解每个子串的最大合法切割次数。1. 状态定义定义f[i][j]表示下标范围为[i, j]闭区间0-based的子串最多可以执行的合法切割次数。2. 前缀和预处理为了快速计算任意子区间内0和1的数量预处理两个前缀和数组p0[i]字符串前i个字符下标0 ~ i-1中字符’0’的总个数。p1[i]字符串前i个字符中字符’1’的总个数。由此可在O(1)时间内得到子串[i, k]中0的个数c0 p0[k1] - p0[i]子串[k1, j]中1的个数c1 p1[j1] - p1[k1]3. 状态转移按区间长度从小到大枚举保证计算长区间时所有子区间的结果已计算完成外层枚举区间长度len从2到n长度为1的区间无法切割初始值为0。中层枚举区间起点i对应终点j i len - 1。内层枚举切割点ki ≤ k j将区间拆分为左右两个子串。若本次切割合法L ≤ |c0 - c1| ≤ R则总切割次数为「本次切割1次 左子串最大切割数 右子串最大切割数」即f [ i ] [ j ] max ⁡ ( f [ i ] [ j ] , 1 f [ i ] [ k ] f [ k 1 ] [ j ] ) f[i][j] \max(f[i][j],\ 1 f[i][k] f[k1][j])f[i][j]max(f[i][j],1f[i][k]f[k1][j])4. 最终结果整个字符串的最大合法切割次数为f[0][n-1]。算法总时间复杂度为O ( n 3 ) O(n^3)O(n3)实际运算量约为n 3 / 6 n^3/6n3/6n500时约2千万次操作完全适配1秒时间限制。总结核心逻辑将大区间的切割问题拆解为两个独立子区间的子问题通过区间DP从小到大合并子问题结果枚举所有合法切割点取最优值。关键操作前缀和快速统计字符数、区间长度从小到大枚举、切割点合法性校验、最大值更新。效率保障区间DP标准实现运算量可控前缀和将单次校验降为O(1)运行效率充足。代码简要说明前缀和数组p0、p1分别存储0和1的前缀计数遍历字符串一次完成初始化支持O(1)区间查询。DP数组初始化二维数组f初始全为0对应所有长度为1的区间切割次数为0的边界条件。三重循环DP最外层按区间长度len从小到大遍历保证子问题先求解。中间层遍历所有起点i计算对应终点j。最内层枚举所有切割点k计算左右段的字符数判断切割合法性合法则更新当前区间的最大切割数。结果输出输出f[0][n-1]即整个字符串的最大切割次数。输入优化关闭流同步加速输入输出适配数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,l,r;cinnlr;string s;cins;vectorllp0(n1,0),p1(n1,0);for(ll i0;in;i){p0[i1]p0[i](s[i]0);p1[i1]p1[i](s[i]1);}vectorvectorllf(n,vectorll(n,0));for(ll len2;lenn;len){for(ll i0;in-len;i){ll jilen-1;for(ll ki;kj;k){ll c0p0[k1]-p0[i];ll c1p1[j1]-p1[k1];ll diffabs(c0-c1);if(diffldiffr)f[i][j]max(f[i][j],1f[i][k]f[k1][j]);}}}coutf[0][n-1]endl;return0;}