/*
初始的想法如下：
維護(hù)一個(gè)棧，使得：
h[stack[0]] < h[stack[1]] < h[stack[2]] < ... < h[stack[top]]
先在h[]的兩端加上哨兵，h[0] = -1 , h[n+1] = -1。
初始時(shí),stack[0] = 0 , top = 0 。
當(dāng)計(jì)算第i個(gè)柱子的L值時(shí)，
先從棧頂依次彈出比h[i]高或等于的柱子。
此時(shí)，滿足：（從棧的維護(hù)過(guò)程可以得知）
h[stack[top]]=h[i]
并且：
h[(stack[top]+1)...(stack[top + 1])]均>=h[i]
也就是L[i] = stack[top]+1
繼續(xù)維護(hù)這個(gè)棧的結(jié)構(gòu)，把i入棧。
對(duì)R的處理也是類似。
在這個(gè)過(guò)程中，實(shí)際上求L[i]=L[L[i]-1] 加速了求取的過(guò)程！
采用了并查集中的路徑壓縮
在實(shí)際操作中，我們是對(duì)每一個(gè)high[i]進(jìn)行枚舉，L[i]保存的是以high[i]為高度時(shí)，左邊可以達(dá)到的最小值
R[i]保存的是以high[i]為高度時(shí)，右邊可以達(dá)到的最大值。
*/
void RectangularArea(int n)
{
vector L(n+2,0);
vector R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
int ans = 0;
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
printf("%d\n", ans);
}
Welcome to my blog : www.lxlsosi.tk
POJ 1964
#include <iostream>
#include <vector>
using namespace std;
/*
這個(gè)問(wèn)題可以簡(jiǎn)化成為更簡(jiǎn)單的問(wèn)題，即只考慮等邊長(zhǎng)的情況！！
在通常情況下，把條件設(shè)簡(jiǎn)單，可以得到到更好的結(jié)果。
*/
int Sigma[1005];
long long high[1005];
int n,m;
long long ans=0;
void RectangularArea(int n)
{
vector<int> L(n+2,0);
vector<int> R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
}
int main()
{
//freopen("poj1964.in","r",stdin);
int p;
cin>>p;
for(int l=0;l<p;l++)
{
cin>>m>>n;
ans=0;
memset(Sigma,0,sizeof(Sigma));
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++) Sigma[i]=1+Sigma[i-1];
for(int i=0;i<m;i++)
{
char temp;
for(int i=1;i<=n;i++)
{
scanf("%c",&temp);
cin>>temp;
if(temp=='F') high[i]+=1;
else high[i]=0;
}
RectangularArea(n);
}
cout<<3*ans<<endl;
}
return 0;
}
POJ 2082
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct Rect{
int w;
int h;
};
int Sigma[50005];
int high[50005];
int n;
void RectangularArea(int n)
{
vector<int> L(n+2,0);
vector<int> R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
int ans = 0;
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
printf("%d\n", ans);
}
int main()
{
// freopen("poj2082.in","r",stdin);
while(cin>>n && n!=-1)
{
vector<Rect> C(n);
for(int i=0;i<n;i++){
scanf("%d%d",&C[i].w,&C[i].h);
}
// 初始化Sigma 和 high
memset(Sigma,0,sizeof(Sigma));
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++)
{
Sigma[i]=C[i-1].w+Sigma[i-1];
high[i]=C[i-1].h;
}
RectangularArea(C.size());
}
return 0;
}
POJ 2559
#include <iostream>
#include <vector>
using namespace std;
/*
這個(gè)問(wèn)題可以簡(jiǎn)化成為更簡(jiǎn)單的問(wèn)題，即只考慮等邊長(zhǎng)的情況！！
在通常情況下，把條件設(shè)簡(jiǎn)單，可以回得到更好的結(jié)果。
*/
int Sigma[100005];
long long high[100005];
int n;
void RectangularArea(int n)
{
vector<int> L(n+2,0);
vector<int> R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
long long ans = 0;
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
cout<<ans<<endl;
// printf("%d\n", ans);
}
int main()
{
//freopen("poj2559.in","r",stdin);
while(cin>>n && n!=0)
{
// 初始化Sigma 和 high
memset(Sigma,0,sizeof(Sigma));
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++)
{
scanf("%d",&high[i]);
Sigma[i]=1+Sigma[i-1];
}
RectangularArea(n);
}
return 0;
}
POJ 2796
#include <iostream>
#include <vector>
using namespace std;
/*
測(cè)試數(shù)據(jù)竟然有一組是1 0 。。。。太無(wú)恥了！！
*/
long long Sigma[100005];
long long high[100005];
int n;
int l,r;
long long ans=0;
void RectangularArea(int n)
{
vector<int> L(n+2,0);
vector<int> R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
for (int i = 1; i <= n; i ++)
{
if(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] )>ans)
{
l=L[i];
r=R[i];
}
ans = max( high[i]*(Sigma[R[i]] - Sigma[L[i]-1]) , ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
}
}
int main()
{
//freopen("poj2796.in","r",stdin);
while(cin>>n)
{
l=1;r=1;
// 初始化Sigma 和 high
ans=0;
memset(Sigma,0,sizeof(Sigma));
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++)
{
scanf("%d",&high[i]);
Sigma[i]=Sigma[i-1]+high[i];
}
RectangularArea(n);
cout<<ans<<endl;
cout<<l<<" "<<r<<endl;
}
return 0;
}
POJ 3250
#include <iostream>
#include <vector>
using namespace std;
long long num[80005];
long long high[80005];
int n;
long long ans=0;
#define INF 1000000005
void RectangularArea(int n)
{
vector<int> L(n+2,0);
high[0]=INF; high[n + 1] = INF+1;
for (int i = 1; i <= n; i ++)
{ L[i] =i-1; num[i]=0;}
for (int i = 1; i <= n; i ++)
{
if( high[i]<high[L[i]] ) { num[i]+=num[L[i]]+1; }
else{
while( high[i] >= high[L[i]])
L[i] = L[L[i]];
num[i]+=num[L[i]]+1;
}
}
for (int i = 1; i <= n; i ++)
{
ans += num[i];
}
}
int main()
{
//freopen("poj3250.in","r",stdin);
cin>>n;
ans=0;
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++)
{
scanf("%d",&high[i]);
}
RectangularArea(n);
cout<<ans-n<<endl;
return 0;
}
POJ 3494
#include <iostream>
#include <vector>
using namespace std;
/*
這個(gè)問(wèn)題可以簡(jiǎn)化成為更簡(jiǎn)單的問(wèn)題，即只考慮等邊長(zhǎng)的情況！！
在通常情況下，把條件設(shè)簡(jiǎn)單，可以回得到更好的結(jié)果。
*/
int Sigma[2005];
long long high[2005];
int n,m;
long long ans=0;
void RectangularArea(int n)
{
vector<int> L(n+2,0);
vector<int> R(n+2,0);
high[0] = high[n + 1] = -1; //初始化邊界，防止越界判錯(cuò)
for (int i = 1; i <= n; i ++) //把L[], R[]賦值為本身
{ L[i] =i; R[i] = i;}
for (int i = 1; i <= n; i ++)
while(high[L[i] - 1] >= high[i]) //確定l[i]的最高左位置
L[i] = L[L[i] - 1];
for (int i = n; i >= 1; i --)
while (high[R[i] + 1] >= high[i]) //確定r[i]的最高右位置
R[i] = R[R[i] + 1];
for (int i = 1; i <= n; i ++)
ans = max(high[i] * (Sigma[R[i]] - Sigma[L[i]-1] ), ans); //得到最大的連續(xù)矩形面積（單位長(zhǎng)度是1）
}
int main()
{
//freopen("poj3494.in","r",stdin);
while(cin>>m>>n)
{
ans=0;
memset(Sigma,0,sizeof(Sigma));
memset(high,0,sizeof(high));
for(int i=1;i<=n;i++) Sigma[i]=1+Sigma[i-1];
for(int i=0;i<m;i++)
{
int temp;
for(int i=1;i<=n;i++)
{
scanf("%d",&temp);
if(temp==1) high[i]+=1;
else high[i]=0;
}
RectangularArea(n);
}
cout<<ans<<endl;
}
return 0;
}