题目描述
jackle 在校赛的时候出过一道 "切割 01 串" 的题目,如今他又出了一道切割 01 串的题目:
给定一个长度为 nnn 的 010101 串,定义如下操作为一次 "切割":
- 将长度大于 111 的字符串分割为两个非空的连续字串,记分割出来的左侧字串 aaa 中 000 的出现次数为 C0C_0C0,右侧字串 bbb 中 111 出现的次数为 C1C_1C1,需要满足 L≤∣C0−C1∣≤RL\leq |C_0-C_1|\leq RL≤∣C0−C1∣≤R。
你每次切割完,都会得到两个新 010101 串,你可以继续选择这些已经被你切出来的 010101 串做切割,只要满足切割条件。
jackle 想问你最多可以切割多少次?
输入描述:
第一行输入 333 个整数,n (1≤n≤500)n\ (1\leq n \leq 500)n (1≤n≤500),L,R (0≤L≤R≤500)L,R\ (0\leq L \leq R \leq 500)L,R (0≤L≤R≤500),分别表示字符串长度,和题目中的两个参数。 第二行输入 111 个长度为 nnn 的 010101 串。
输出描述:
输出最多能切割多少次?
示例1
输入
复制6 2 3 011011
6 2 3 011011
输出
复制3
3
说明
其中一种切割次数最多的切法如下: 第一次切割可以切:0 ∣ 110110\ |\ 110110 ∣ 11011,然后选择 110111101111011 这个串继续做切割。 第二次切割可以切:1 ∣ 10111\ |\ 10111 ∣ 1011,然后选择 101110111011 这个串继续做切割。 第三次切割可以切:1 ∣ 0111\ |\ 0111 ∣ 011。
做法
第一次遇到区间dp。开始我是用bfs写的,把每个分割的区间丢进队列,结果内存超限了。感觉区间dp像分治,把问题分割成多个子问题,然后求解子问题,最后合并子问题得出原问题的答案。之前分治是用递归,数据范围大一点就是区间dp了。
#include<bits/stdc++.h>
using namespace std;
int n,L,R,dp[510][510],c0[510],c1[510];
string s;
int main(){
cin>>n>>L>>R;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++){
c1[i]=c1[i-1];
c0[i]=c0[i-1];
if(s[i]=='1') c1[i]++;
else c0[i]++;
}
for(int len=1;len<=n;len++){//区间长度
for(int l=1;l<=n;l++){
int r=l+len-1;//利用区间长度算出r
if(r>n) break;
for(int k=l;k<=r-1;k++){//切割区间
int C0=c0[k]-c0[l-1];
int C1=c1[r]-c1[k];
if(L<=abs(C1-C0)&&abs(C0-C1)<=R)
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+1);
}
}
}
cout<<dp[1][n];
}