久久久久久久99精品免费观看,日本久久中文字幕,性高湖久久久久久久久AAAAA

公告

記錄我的生活和工作。。。

2010年10月

日

一

二

三

四

五

六

統計

隨筆 - 182
文章 - 1
評論 - 41
引用 - 0

留言簿(10)

隨筆分類(70)

隨筆檔案(182)

文章檔案(1)

2011年1月 (1)

如影隨形

小樂 CppBlog
小樂 CSDN
小樂 Github
小樂博客園
小樂豆瓣

搜索

閱讀排行榜

評論排行榜

連續區域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494

/*

初始的想法如下：
 維護一個棧，使得：
h[stack[0]] < h[stack[1]] < h[stack[2]] < ... < h[stack[top]]

先在h[]的兩端加上哨兵，h[0] = -1 , h[n+1] = -1。

初始時,stack[0] = 0 , top = 0 。

當計算第i個柱子的L值時，
先從棧頂依次彈出比h[i]高或等于的柱子。
此時，滿足：（從棧的維護過程可以得知）
h[stack[top]]=h[i]
并且：
h[(stack[top]+1)...(stack[top + 1])]均>=h[i]
也就是L[i] = stack[top]+1

繼續維護這個棧的結構，把i入棧。

對R的處理也是類似。

在這個過程中，實際上求L[i]=L[L[i]-1] 加速了求取的過程！
采用了并查集中的路徑壓縮

在實際操作中，我們是對每一個high[i]進行枚舉，L[i]保存的是以high[i]為高度時，左邊可以達到的最小值 
R[i]保存的是以high[i]為高度時，右邊可以達到的最大值。 
*/
void RectangularArea(int n)
{
	vector L(n+2,0);
	vector R(n+2,0);
	high[0] = high[n + 1] = -1;               //初始化邊界，防止越界判錯

	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); //得到最大的連續矩形面積（單位長度是1）
	printf("%d\n", ans);
}

Welcome to my blog : www.lxlsosi.tk

POJ 1964

#include <iostream>
#include <vector>
using namespace std;

/*
這個問題可以簡化成為更簡單的問題，即只考慮等邊長的情況！！
在通常情況下，把條件設簡單，可以得到到更好的結果。
*/
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;              //初始化邊界，防止越界判錯

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); //得到最大的連續矩形面積（單位長度是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;               //初始化邊界，防止越界判錯

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); //得到最大的連續矩形面積（單位長度是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;

/*
這個問題可以簡化成為更簡單的問題，即只考慮等邊長的情況！！
在通常情況下，把條件設簡單，可以回得到更好的結果。
*/
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;              //初始化邊界，防止越界判錯

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); //得到最大的連續矩形面積（單位長度是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;

/*
測試數據竟然有一組是1 0 。。。。太無恥了！！
*/
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;              //初始化邊界，防止越界判錯

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); //得到最大的連續矩形面積（單位長度是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;

/*
這個問題可以簡化成為更簡單的問題，即只考慮等邊長的情況！！
在通常情況下，把條件設簡單，可以回得到更好的結果。
*/
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;              //初始化邊界，防止越界判錯

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); //得到最大的連續矩形面積（單位長度是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;
}

posted on 2011-05-30 15:02 Sosi 閱讀(853) 評論(0) 編輯收藏引用所屬分類: Algorithm

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: Timus 1078 最長路Floyd POJ 3268 POJ 1860 SPFA 最長路 POJ 3159 SPFA 一道網易游戲筆試題 SRM 304 U SRM 303U 算24點算法 SRM 522 連續區域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

O(1) 的小樂

公告

統計

留言簿(10)

隨筆分類(70)

隨筆檔案(182)

文章檔案(1)

如影隨形

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

連續區域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494