題意：

給三個整數n，l，r，和一個字符串s，滿足l<=|c0-c1|<=r就可以切成字符串a和字符串b，c0為字符串a左側出現0的次數，c1為字符串b右側出現1的次數，求最多切割次數

知識點：區間dp

分析：先用前綴和求出數組c1和c0，假設我們在k點進行切割，就可以每次更新dp[l][r]，先算出左區間[l,k]的0的個數為c00=c0[k]-c0[l-1]，算出右區間[k+1,r]的1的個數為c11=c1[r]-c1[k]，符合條件的每次更新區間dp，核心代碼dp[l][r]=max(dp[l][r],1+dp[l][k]+dp[k+1][r])。

#include<bits/stdc++.h>
using namespace std;
int dp[510][510],c0[510],c1[510];
int main(){
?? ?int n,L,R;cin>>n>>L>>R;string s;cin>>s;
?? ?for(int i=1;i<=n;i++){
?? ??? ?c1[i]=c1[i-1];
?? ??? ?c0[i]=c0[i-1];
?? ??? ?if(s[i-1]=='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;
?? ??? ??? ?if(r>n)break;
?? ??? ??? ?for(int k=l;k<r;k++){
?? ??? ??? ??? ?int c00=c0[k]-c0[l-1];
?? ??? ??? ??? ?int c11=c1[r]-c1[k];
?? ??? ??? ??? ?if(abs(c00-c11)>=L&&abs(c00-c11)<=R){
?? ??? ??? ??? ??? ?dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+1);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?cout<<dp[1][n];
}