TIOJ 1550 鏡框設置回來了!

 poao899    72K    2246MS    G++     0.63K     2010-03-27 18:24:24                                       .


第一個複雜度很好想但是一定會TLE= =





















O(nm lg m) -> O(nm)


//***************************

先counting一下，然後檢查每個(上次有出現的數字+1)這次有沒有出現

//***************************

#include <stdio.h>
int dp[1600],n,m,t,max,count[16000];
int l1[1600],l2[1600],top,otop,cnt;
int main(){
	int *old=l1,*list=l2,*tmp;
	scanf("%d%d\n",&n,&m);
	for(int i=0; i
		top=cnt=0;
		for(int j=0; j
			count[old[j]]=0;
		for(int j=0; j
			getchar()=='1'? dp[j]++: dp[j]=0;
			count[dp[j]]++;
		}
		getchar();
		if(count[1])list[top++]=1;
		for(int j=0; j
			if(count[ old[j]+1 ])
				list[top++]= old[j]+1;
		for(int j=top-1;j>=0;j--){
			cnt+=count[ list[j] ];
			t=cnt*list[j];
			if(t>max)max=t;
		}
		tmp=old; old=list; list=tmp; otop=top;
	}
	printf("%d\n",max);
}