01背包的变形/拓展（这道题其实是二维背包）

//头文件
int n,k;
string str;
//f[i][j] //在前i天已经工作了j天
//f[i][j][p] //多了一维p（现在已经连续工作了多少天）
//f[j][p] //采用就地滚动去掉第一维
int f[405][405];
int main(){
read(n);read(k);
cin >> str;
//int len=str.size();
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;++i){
for(int j=i;j>0;--j){
for(int p=1;p<=j;++p){
//f[j][0]表示这一天休息
f[j][0]=min(f[j][0],f[j][p]); //f[i][j][0]=min( f[i][j][0] , min(f[i-1][j][0],f[i-1][j][p]) );
if(str[i-1]=='1')
f[j][p]=min(f[j][p],f[j-1][p-1]+p); //f[i][j][p]=min(f[i-1][j][p],f[i][j-1][p-1]+p);
}
}
}
for(int j=n;j>0;--j){
for(int p=j;p>=0;--p){
if(f[j][p]<=k){
cout << j;
return 0;
}
}
}
cout << 0;
return 0;
}