【牛客算法周周练7】Rabbit的工作(1)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 405;
int dp[2][N][N];//dp(i,j,k)表示前i天工作了j天且已经连续工作了k天花费的最小体力值
char s[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",s + 1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 0;j <= i;j++){
            dp[i & 1][j][0] = dp[i-1 & 1][j][0];
            for(int k = 1;k <= j;k++){
                dp[i & 1][j][0] = min(dp[i & 1][j][0],dp[i-1 & 1][j][k]);
                if(s[i] == '1'){
                    dp[i & 1][j][k] = min(dp[i & 1][j][k],dp[i-1&1][j-1][k-1] +k);
                }
            }
        }
    } 
    for(int i = n;i >= 0;i--){
        for(int j = 0;j <= i;j++){
            if(dp[n & 1][i][j] <= m){
                printf("%d\n",i);
                return 0;
            }
        }
    }
    return 0;
}