生活随笔
收集整理的這篇文章主要介紹了
152. 城市游戏【单调栈】
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
131. 直方圖中最大的矩形 這一道題的變種。我們只多了枚舉所有的地面
#include<bits/stdc++.h>
using namespace std
;
const int N
=1010;
int s
[N
][N
],a
[N
],n
,m
;
char c
[N
][N
];
int solve(int x
)
{for(int i
=1;i
<=m
;i
++) a
[i
]=s
[x
][i
];int lmin
[N
]={0},rmin
[N
]={0};a
[0]=-1,a
[m
+1]=-1;stack
<int>st
; st
.push(0);for(int i
=1;i
<=m
;i
++){while(st
.size()&&a
[st
.top()]>=a
[i
]) st
.pop();lmin
[i
]=st
.top();st
.push(i
);}while(st
.size()) st
.pop();st
.push({m
+1});for(int i
=m
;i
>=1;i
--){while(st
.size()&&a
[st
.top()]>=a
[i
]) st
.pop();rmin
[i
]=st
.top();st
.push(i
);}int ans
=0;for(int i
=1;i
<=m
;i
++) ans
=max(ans
,a
[i
]*(rmin
[i
]-lmin
[i
]-1));return ans
;
}
int main(void)
{cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++){for(int j
=1;j
<=m
;j
++){cin
>>c
[i
][j
];if(c
[i
][j
]=='F') s
[i
][j
]=s
[i
-1][j
]+1;else s
[i
][j
]=0;}}int res
=0;for(int i
=1;i
<=n
;i
++) res
=max(res
,solve(i
));cout
<<res
*3<<endl
;return 0;
}
總結(jié)
以上是生活随笔為你收集整理的152. 城市游戏【单调栈】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
