题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
下面的代码 没有各种封装函数 单纯该写啥写啥 不需要反转
还是不熟悉 需要注意存储的是下标还是数据 此题中 g[n]存的是下标 浪费半天时间
看了Y总的代码 对间距的处理有了更深的理解 每次找它在范围内的边缘点即可 最后右边减去右边加一
可以设置栈底为0 或者-1 根据题意 可以使代码更简洁 不需要判空等
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
char pic[N][N];
int h[N][N], l[N], r[N], g[N];
int n, m;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
{
char s;
cin >> s;
pic[i][j] = s;
if(pic[i][j] != 'R') h[i][j] = h[i - 1][j] + 1;
else h[i][j] = 0;
}
int res = 0;
for(int i = 1; i <= n; i ++ )
{
int tt = 0;
g[0] = -1;
for(int j = 1; j <= m; j ++ ) {
while(h[i][g[tt]] >= h[i][j] && tt != 0) tt --;
if(tt != 0) l[j] = g[tt] + 1;
else l[j] = 1;
g[++ tt] = j;
}
tt = 0;
for(int j = m; j >= 1; j -- ) {
while(h[i][g[tt]] >= h[i][j] && tt != 0) tt --;
if(tt != 0) r[j] = g[tt] - 1;
else r[j] = m;
g[++ tt] = j;
}
for(int j = 1; j <= m; j ++ ){
res = max(res, h[i][j] * (r[j] - l[j] + 1) );
}
}
cout << res * 3 << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla