记录编号	417300	评测结果	AAAAAAAA
题目名称	抓苹果	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-06-24 19:54:45	内存使用	0.88 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline char getc(void){
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int in(void){
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res;
}

void dfs(int i);

int T, W, ans;
int s[1010];
int f[1010][40][2];

int main(){ 
#ifndef LOCAL
    freopen("bcatch.in", "r", stdin);
    freopen("bcatch.out", "w", stdout);
#endif
    T = in(), W = in();

    for(int i = 1; i <= T; ++i) s[i] = in();
    dfs(T);
    
    for(int i = 0; i <= W; ++i) ans = max(ans, max(f[T][i][0], f[T][i][1]));

    printf("%d", ans);
    return 0;
}

void dfs(int i){
    if(i == 1){
        if(s[1] == 1) f[1][W][0] = 1;
        else f[1][W][1] = 1;
        return ;
    }

    dfs(i - 1);
    if(s[i] == 1){
        f[i][W][0] = f[i - 1][W][0] + 1;
        f[i][W][1] = f[i - 1][W][1];
        for(int j = 0; j < W; ++j){
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j + 1][1]) + 1;
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j + 1][0]);
        }
    } else {
        f[i][W][0] = f[i - 1][W][0];
        f[i][W][1] = f[i - 1][W][1] + 1;
        for(int j = 0; j < W; ++j){
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j + 1][1]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j + 1][0]) + 1;
        }
    }

    return ;
}