poj 1964 City Game

http://poj.org/problem?id=1964

dp

题目的意思就是找出一个最大的矩形, 这个矩形由F组成, 最后的答案就是max*3.

思路: 逐行的加入, 每次加入求能构成的最大矩形....

用数组height[i]表示: 当前行如果加入这第i列所能构成的矩形的最大高度.

数组left[i]表示: 向左延伸, 高度小于当前列的第一个列坐标

数组right[i]表示: 向右延伸, 高度小于当前列的第一个列坐标.

初始化:

left[0] = left[m+1] = -1;

right[0] = right[m+1] = -1; //其中m表示列数

这题要特别注意输入数据格式, 两个字符间可能有多个空格.....-_-||

#include<stdio.h>
#include<string.h>
#define MAXN 1002
int height[MAXN];	//列高
int left[MAXN], right[MAXN];
int n, m;
int dp() {
	int i, j;
	//计算左边节点
	left[0] = left[m+1] = -1;
	for(i=1; i<=m; i++) {
		if(height[i] == 0) {
			continue;
		}
		for(j=i-1; ; j=left[j]) {
			if(height[j] < height[i]) {
				left[i] = j;
				break;
			}
		}
	}
	//计算右边节点
	right[0] = right[m+1] = -1;
	for(i=m; i>=1; i--) {
		if(height[i] == 0) {
			continue;
		}
		for(j=i+1; ; j=right[j]) {
			if(height[j] < height[i]) {
				right[i] = j;
				break;
			}
		}
	}
	//计算当前能得到的最大矩形面积
	int cnt = 0;
	int max = 0;
	for(i=1; i<=m; i++) {
		if(height[i] != 0) {
			cnt = (right[i] - left[i] - 1) * height[i];
			if(cnt > max) {
				max = cnt;
			}
		}
	}
	return max;
}
int main() {
//freopen("in.txt", "r", stdin);
	int t;
	char c[10];
	scanf("%d", &t);
	while(t--) {
		memset(height, 0, sizeof(height));
		memset(left, 0, sizeof(left));
		memset(right, 0, sizeof(right));
		scanf("%d%d", &n, &m);
		int i, j;
		int max = 0, tmp;
		for(i=1; i<=n; i++) {
			for(j=1; j<=m; j++) {
				//scanf("%*c%c", &c);
				scanf("%s", c);
				if(c[0] == 'F') {
					height[j]++;
				} else {
					height[j] = 0;
				}
			}
			tmp = dp();
			if(max < tmp) {
				max = tmp;
			}
		}
		printf("%d/n", max * 3);
	}
	return 0;
}

买一送一题: poj 3494