比赛 20120711 评测结果 AAAAAAAEEEEE
题目名称 平衡奶牛 最终得分 58
用户昵称 ZhouHang 运行时间 1.369 s
代码语言 C++ 内存使用 120.93 MiB
提交时间 2012-07-11 10:43:24
显示代码纯文本
/**
*Prob	: balline
*Data	: 2012-7-11
*Sol	: 枚举骗分
*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

struct node{
	int a[31];
} num[1010][1010];

int n,k;
int f[1010],g[1010];


int init(node &x,int y)
{
	int tmp = 0;
	while (y!=0) {
		tmp ++;
		x.a[tmp] = y%2;
		y /= 2;
	}
}

bool check(int x,int y)
{
	for (int i=2; i<=k; i++)
	 if (num[x][y].a[i]!=num[x][y].a[i-1]) return false;
	return true;
}

int main()
{
	freopen("balline.in","r",stdin);
	freopen("balline.out","w",stdout);
	
	scanf("%d%d",&n,&k);
	int tmp;
	memset(num,0,sizeof(num));
	for (int i=1; i<=n; i++) {
		scanf("%d",&tmp);
		if (tmp) f[i] = 0;
		else f[i] = 1;
		g[i] = i;
		init(num[i][i],tmp);
	}

	for (int i=2; i<=n; i++)
	 for (int j=i; j>=1; j--) {
		for (int q=1; q<=k; q++)
			num[j][i].a[q] = num[j][j].a[q] + num[j+1][i].a[q];
		if (check(j,i)) {
			g[i] = j; f[i] = i-j+1;
		}
	 }
	 
	int ans = 0;
	for (int i=1; i<=n; i++)
		ans = max(ans,f[i]);
	
	printf("%d\n",ans);
	
	fclose(stdin); fclose(stdout);
	return 0;
}