记录编号	166636	评测结果	AAAAAAAA
题目名称	1998.抓苹果	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-06-15 21:31:49	内存使用	4.12 MiB

#include <cstdio>

using namespace std;

int T,w,out;
int a[1001][3];
int f[1001][1001];

inline int in() {
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(; c>='0'&&c<='9'; c=getchar())x=x*10+c-'0';
	return x;
}

inline int max(int a,int b){
	return a > b ? a : b;
}

int main() {
	freopen("bcatch.in","r",stdin);
	freopen("bcatch.out","w",stdout);
	int i,j,k,pos;
	T=in();
	w=in();
	for(i=1; i<=T; ++i) {
		pos=in();
		a[i][pos]=1;
	}
	if(a[1][1]==1)
		f[1][0]=1;
	else
	    f[1][0]=0;
	for(i=1; i<=T; ++i)
		for(k=1; k<=i; ++k)
			for(j=0; j<=w; ++j) {
				if(j%2==0)
					f[i][j]=max(f[k-1][j-1],f[k-1][j])+a[i][1];
				else
				    f[i][j]=max(f[k-1][j-1],f[k-1][j])+a[i][2];
				out=max(out,f[i][j]);
				}
	printf("%d",out);
}