pku2385.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 1100
#define ONLINE

#ifndef ONLINE
#include <time.h>
#endif

int Max(int x, int y)
{
	return x < y ? y : x;
}

int main()
{

#ifndef ONLINE
	freopen("PKU2385.in", "r", stdin);
	clock_t start = clock();
#endif
	int T, W;
	int p[size], DP[33][size];
	int i, j, ans;
	while (EOF != scanf("%d %d", &T, &W))
	{
		for (i = 1; i <= T; i++)
		{
			scanf("%d", &p[i]);
			p[i]--;
		}
		memset(DP, 0, sizeof(DP));
		for (i = 1; i <= T; i++)
		{
			DP[0][i] = DP[0][i - 1];
			if (!p[i])
			{
				DP[0][i]++;
			}
		}
		for (j = 1; j <= W; j++)
		{
			for (i = j; i <= T; i++)
			{
				DP[j][i] = Max(DP[j][i - 1], DP[j - 1][i - 1]);
				if (j % 2 == p[i])
					DP[j][i]++;
			}
		}
		ans = 0;
		for (i = 0; i <= W; i++)
		{
			if (ans < DP[i][T])
				ans = DP[i][T];
		}
		printf("%d\n", ans);
	}
#ifndef ONLINE
	printf("TIME:%dms\n", clock() - start);
#endif
	return 0;
}