CSP/NOIP 復習：單調棧
最近模擬賽打的都不是太好，先隨便復習復習吧，馬上就要 CSPS 了，我可以考好的。
這里放一些單調棧的題目，笛卡爾樹先不說，這個我已經忘了，后天復習一下。
本體
棧中維護有單調性的數據，入棧時維護這個單調性，這是計算結果。
是個人都會，不想多寫。
直接進入 dlc 環節。
最大子矩形。
就是一個平面，有一些障礙不能選，要求我們選出來一個最大的，不包含障礙的子矩形，這個就可以使用單調棧來做。
我們先考慮一個弱化版的。
HISTOGRA - Largest Rectangle in a Histogram
這個是簡單的，我們考慮盡可能使用每個位置的最高值，也就是算出來左邊最近的比它矮的位置和右邊最近比它矮的位置。
正確性顯然，最大的矩形肯定盡可能用完了位置。
直接上單調棧，注意初始化左右要大一個。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
bool ed=false;
int stk[MN], top, n, a[MN];
int l[MN], r[MN], ans=0;
void Getl(){
top=0;
for(int i=1; i<=n; ++i){
while(top&&a[stk[top]]>a[i]){
r[stk[top]]=i; --top;
}
stk[++top]=i;
}
}
void Getr(){
top=0;
for(int i=n; i>=1; --i){
while(top&&a[stk[top]]>a[i]){
l[stk[top]]=i; --top;
}
stk[++top]=i;
}
}
void Solve(){
cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
if(n==0){ed=true; return;}
for(int i=1; i<=n; ++i) l[i]=0;
for(int i=1; i<=n; ++i) r[i]=n+1;
Getl(); Getr(); ans=0;
for(int i=1; i<=n; ++i){
ans=max(ans,(r[i]-l[i]-1)*a[i]);
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
while(!ed) Solve();
return 0;
}
換到二維上就很簡單了，對于每一個高度跑一遍就行了。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=3145;
char mp[MN][MN];
int n, m, h[MN][MN];
int stk[MN], top=0;
int l[MN], r[MN], ans=0;
void Read(){
cin>>n>>m;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
cin>>mp[i][j];
}
}
for(int i=1; i<=n; ++i){
for(int j=m; j>=1; --j){
h[i][j]=h[i][j+1]+1;
if(mp[i][j]=='R') h[i][j]=0;
}
}
}
void Getr(int height){
top=0;
for(int i=1; i<=n; ++i) r[i]=n+1;
for(int i=1; i<=n; ++i){
while(top&&h[stk[top]][height]>h[i][height]){
r[stk[top]]=i; --top;
}
stk[++top]=i;
}
}
void Getl(int height){
top=0;
for(int i=1; i<=n; ++i) l[i]=0;
for(int i=n; i>=1; --i){
while(top&&h[stk[top]][height]>h[i][height]){
l[stk[top]]=i; --top;
}
stk[++top]=i;
}
}
void Solve(){
Read();
for(int height=1; height<=m; ++height){
Getl(height); Getr(height);
for(int i=1; i<=n; ++i){
//cout<<l[i]<<" "<<r[i]<<" | ";
ans=max(ans,(r[i]-l[i]-1)*(h[i][height]));
}
}
cout<<ans*3<<'\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
Solve();
return 0;
}
浙公網安備 33010602011771號