2385.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 1004
int a[NMAX][35][2]={0};
int m[NMAX];
int T,W;
int max(int a,int b)
{
	return a>b?a:b;
}
void solve()
{
	int i,j,p;
	if(m[1]==0)
		a[1][0][0]=1;
	else
		a[1][1][1]=1;
	for(i=2;i<=T;i++)
	{
		for(p=0;p<2;p++)
		{
			if(p==m[i])
				a[i][0][p]=a[i-1][0][p]+1;
			else
				a[i][0][p]=a[i-1][0][p];
		}
		for(j=1;j<=W;j++)
		{
			for(p=0;p<2;p++)
			{
				if(m[i]==p)
					a[i][j][p]=max(a[i-1][j][p],a[i-1][j-1][!p])+1;
				else
					a[i][j][p]=max(a[i-1][j][p],a[i-1][j-1][!p]);
			}
		}
	}
	int max=0;
	for(i=0;i<=T;i++)
		for(j=0;j<=W;j++)
			for(p=0;p<2;p++)
				if(max<a[i][j][p])
					max=a[i][j][p];
	printf("%d",max);
}

int main()
{
	
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i;
	scanf("%d%d",&T,&W);
	if(T<W)
	{
		printf("%d",T);
		return 1;
	}
	for(i=1;i<=T;i++)
	{
		scanf("%d",&m[i]);
		m[i]--;
	}
	solve();

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}