首页 > 代码库 > Codeforces Round #221 (Div. 2) D

Codeforces Round #221 (Div. 2) D

有点郁闷的题目,给了2000ms,可是n,m的范围已经是5000了。5000 * 5000一般在别的OJ已经是超了2000ms,一開始不敢敲。看了下别人有n*m的潜逃循环,原来CF的机子如此的强大,一開始题意没看清错了,原来随意行能够交换,列不行

那就先dp出 每一行的 每个位置包含它本身以及前面的连续出现1的长度。然后再对列进行处理。由于列是不能变的。所以相应列是固定的,那么就对列枚举,然后由于行能够交换。所以详细哪一列在哪一行能够变化。就把前面dp出的最大的放在最后面,意思就是呈现一个倒着放的梯形 当然也有可能是矩形,在中求一个面积最大的矩形就可以,



int n,m;

char mp[5000 + 55][5000 + 55];

int dp[5000 + 55][5000 + 55];

void init() {
	memset(mp,0,sizeof(mp));
	memset(dp,0,sizeof(dp));
}

bool input() {
	while(scanf("%d %d",&n,&m) == 2) {
		for(int i=1;i<=n;i++) 
			scanf("%s",mp[i] + 1);
		return false;
	}
	return true;
}

void cal() {
	for(int i=1;i<=n;i++) {
		dp[i][0] = 0;
		for(int j=1;j<=m;j++)
			dp[i][j] =  mp[i][j] == ‘1‘?

dp[i][j - 1] + 1:0; } int ans = 0; for(int j=1;j<=m;j++) { int tmp[5000 + 55]; for(int i=1;i<=n;i++)tmp[i] = dp[i][j]; sort(tmp + 1,tmp + n + 1); for(int i=1;i<=n;i++)ans =max(ans,tmp[i] * (n - i + 1)); } cout<<ans<<endl; } void output() { } int main () { while(true) { init(); if(input())return 0; cal(); output(); } }




Codeforces Round #221 (Div. 2) D