#include"stdio.h"
#include"string.h"
#define max 1004
int re[40][max];
int r[max];
bool rf[max];
int check[max];
int ch[max];
int main()
{
    int t,w,i,co,f,j,rl,rr,le,ma,k,kkk;
    bool fg;
    while(scanf("%d%d",&t,&w)!=EOF)
    {
        j=1;ma=0;
        memset(r,0,sizeof(r));
        memset(re,0,sizeof(re));
		memset(check,1,sizeof(check));memset(ch,0,sizeof(ch));
        scanf("%d",&f);
        if(f==1) fg=true;else fg=false;
        co=1;
        for(i=1;i<t;i++)
        {
		    scanf("%d",&f);
            if(f==1&&fg==true){co++;continue;}
            else if(f==1&&fg==false) {
                r[j++]=co;co=1;rf[j-1]=false;fg=true;continue; }
            else if(f==2&&fg==false) {co++;continue;}
            else if(f==2&&fg==true) {
                r[j++]=co;co=1;rf[j-1]=true;fg=false; }
        }
		r[j]=co;rf[j]=fg;
        le=j;
        rl=0;rr=0;if(rf[1]==false) {check[1]=0;r[1]=0;}
		for(i=1;i<=le;i++)
        {
		       if(rf[i])
			      if(rf[1])
			           for(j=1;j<=i;j+=2)re[0][i]+=r[j];
				     else for(j=2;j<=i;j+=2)re[0][i]+=r[j];
			   else re[0][i]=re[0][i-1]; 
			   check[i]=1;
        }if(rf[1]==false) check[1]=0;
        for(i=1;i<=w;i++) {
            for(j=1;j<=le;j++) {
			      re[i][j]=re[i-1][j];ch[j]=check[j];
	            for(k=j-1;k>0;k--) 
				   if(rf[j]) {
  				      if(ch[k]==0)
                        if(re[i-1][k]+r[j]>re[i][j]){re[i][j]=re[i-1][k]+r[j];ch[j]=1;}
						    }
					else if(ch[k]==1) 
						    if(re[i-1][k]+r[j]>re[i][j]){re[i][j]=re[i-1][k]+r[j];ch[j]=0;} 
				kkk=r[j];
				for(k=j-1;k>0;k--){
				   if(ch[k]==rf[j]) {
			        	if(re[i][j]<re[i][k]+kkk){ re[i][j]=re[i][k]+kkk;ch[j]=ch[k];} }
					else if(re[i][j]<re[i][k]) { re[i][j]=re[i][k];ch[j]=ch[k];}
				}
				for(k=1;k<=le;k++) check[k]=ch[k];
				if(re[i][j]>ma) ma=re[i][j];
				}
		}
        printf("%d\n",ma);
    }
    return 0;
}

• 每次只有一组数据,单case输入的 (2092) Iamjw 2006-12-06 21:07:14