丁香久久婷婷国产午夜视频,999久久久免费国产精品播放,久久99九九国产免费看小说

公告

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

2011年5月

日

一

二

三

四

五

六

統(tǒng)計(jì)

隨筆 - 182
文章 - 1
評(píng)論 - 41
引用 - 0

留言簿(10)

隨筆分類(lèi)(70)

隨筆檔案(182)

文章檔案(1)

2011年1月 (1)

如影隨形

小樂(lè) CppBlog
小樂(lè) CSDN
小樂(lè) Github
小樂(lè) 博客園
小樂(lè) 豆瓣

搜索

閱讀排行榜

評(píng)論排行榜

連續(xù)區(qū)域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494

/*

初始的想法如下：
 維護(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的處理也是類(lèi)似。

在這個(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;
}

posted on 2011-05-30 15:02 Sosi 閱讀(856) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): Algorithm

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: Timus 1078 最長(zhǎng)路Floyd POJ 3268 POJ 1860 SPFA 最長(zhǎng)路 POJ 3159 SPFA 一道網(wǎng)易游戲筆試題 SRM 304 U SRM 303U 算24點(diǎn)算法 SRM 522 連續(xù)區(qū)域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

O(1) 的小樂(lè)

公告

統(tǒng)計(jì)

留言簿(10)

隨筆分類(lèi)(70)

隨筆檔案(182)

文章檔案(1)

如影隨形

搜索

最新隨筆

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

連續(xù)區(qū)域最大矩形面積 POJ 1964 2082 2559 2796 3250 3494