单调栈 不知道为什么7 8 9测试点 wa
  • 板块P4147 玉蟾宫
  • 楼主telankesi
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/6 20:37
  • 上次更新2023/11/3 11:16:55
查看原帖
单调栈 不知道为什么7 8 9测试点 wa
866969
telankesi楼主2023/7/6 20:37
#define _CRT_SECURE_NO_WARNINGS 1
#include <string.h>
#include <queue>
#include <stdio.h>
#include <stack>
#include <iostream>
#define INF 1000009
#define MAX 100100
#define ll long long  
using namespace std;
int n, m;
char map[1011][1011];
int pos[1011][1011];
int d[1011];
int main() {
	int st[10100];
	int head = 0;
	int flag = 0;
	scanf("%d %d", &n, &m);
	char ch;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'F') {
				pos[i][j] = 1 + pos[i - 1][j];
				flag = 1;
			}
			else pos[i][j] = 0;
		}
	}
	if (!flag) {
		printf("0");
		return 0;
	}
	int maxans = 1;
	int top;
		for (int i = 1; i <= n; i++) {
		int ans = 0;
		for (int j = 1; j <= m; j++) {
			if (head > 0) {
				top = st[head];
			}
			
			int num = 0;
			while (head > 0 && pos[i][top] >= pos[i][j]) {
				ans = max(ans, pos[i][top] * d[head]);
				num += d[head];
				head--;
				top = st[head];
			}
			st[++head] = j;
			d[head] = num+1;

		}
		while(head>0) {
			top = st[head];
			ans = max(ans, pos[i][top] * d[head]);
			head--;
			d[head] += d[head + 1];
		}
	    maxans = max(maxans,ans);
	}
		cout << maxans*3;
	return 0;
}
2023/7/6 20:37
加载中...