• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            M.J的blog

            algorithm,ACM-ICPC
            隨筆 - 39, 文章 - 11, 評論 - 20, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 2762. Balanced Lineup (區(qū)間求最值sparsetable算法)

            啥也不說了,sparsetable算法的高效性,我真佩服那個(gè)發(fā)明它的人。Orz...

            以下是關(guān)于這個(gè)算法的講解(我也沒理解透,回頭細(xì)細(xì)品味吧)

            RMQ(Range Minimum/Maximum Query)問題是求區(qū)間最值問題。你當(dāng)然可以寫個(gè)O(n)的(怎么寫都可以吧=_=),但是萬一要詢問最值1000000遍,估計(jì)你就要掛了。這時(shí)候你可以放心地寫一個(gè)線段樹(前提是不寫錯(cuò))O(logn)的復(fù)雜度應(yīng)該不會掛。但是,這里有更牛的算法,就是ST算法,它可以做到O(nlogn)的預(yù)處理,O(1)!!!地回答每個(gè)詢問。

                   來看一下ST算法是怎么實(shí)現(xiàn)的(以最大值為例):

                   首先是預(yù)處理,用一個(gè)DP解決。設(shè)a[i]是要求區(qū)間最值的數(shù)列,f[i, j]表示從第i個(gè)數(shù)起連續(xù)2^j個(gè)數(shù)中的最大值。例如數(shù)列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1個(gè)數(shù)起,長度為2^0=1的最大值,其實(shí)就是3這個(gè)數(shù)。f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……從這里可以看出f[i,0]其實(shí)就等于a[i]。這樣,Dp的狀態(tài)、初值都已經(jīng)有了,剩下的就是狀態(tài)轉(zhuǎn)移方程。我們把f[i,j]平均分成兩段(因?yàn)閒[i,j]一定是偶數(shù)個(gè)數(shù)字),從i到i+2^(j-1)-1為一段,i+2^(j-1)到i+2^j-1為一段(長度都為2^(j-1))。用上例說明,當(dāng)i=1,j=3時(shí)就是3,2,4,5 和 6,8,1,2這兩段。f[i,j]就是這兩段的最大值中的最大值。于是我們得到了動規(guī)方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1]).

             

            接下來是得出最值,也許你想不到計(jì)算出f[i,j]有什么用處,一般毛想想計(jì)算max還是要O(logn),甚至O(n)。但有一個(gè)很好的辦法,做到了O(1)。還是分開來。如在上例中我們要求區(qū)間[2,8]的最大值,就要把它分成[2,5]和[5,8]兩個(gè)區(qū)間,因?yàn)檫@兩個(gè)區(qū)間的最大值我們可以直接由f[2,2]和f[5,2]得到。擴(kuò)展到一般情況,就是把區(qū)間[L,R]分成兩個(gè)長度為2^n的區(qū)間(保證有f[i,j]對應(yīng))。直接給出表達(dá)式:

            k := ln(R-L+1) / ln(2);

            ans := max(F[L,k], F[R - 2^k+1, k]);

            這樣就計(jì)算了從i開始,長度為2^t次的區(qū)間和從r-2^i+1開始長度為2^t的區(qū)間的最大值(表達(dá)式比較煩瑣,細(xì)節(jié)問題如加1減1需要仔細(xì)考慮.

            Code:

             1 #include<iostream>
             2 #include<cmath>
             3 #define M 100005
             4 int rmq1[M][30];
             5 int rmq2[M][30];
             6 int a[M];
             7 int N,Q,R,L;
             8 using namespace std;
             9 int max(int a,int b)
            10 {
            11     if(a>b) return a;
            12     else   return b;
            13 }
            14 int min(int a,int b)
            15 {
            16     if(a<b) return a;
            17     else    return b;
            18 }
            19 void DP(int N)
            20 {
            21     int i,j,k;
            22     for(i=1;i<=int(log(double(N))/log(2.0));i++)
            23         for(j=1;j<=N;j++)
            24         {
            25             rmq1[j][i]=max(rmq1[j][i-1],rmq1[j+int(pow(2.0,i-1))][i-1]);
            26             rmq2[j][i]=min(rmq2[j][i-1],rmq2[j+int(pow(2.0,i-1))][i-1]);
            27         }
            28 }
            29 int search(int i,int j)
            30 {
            31      int k=(int)(log((double)(j-i+1))/log(2.0));
            32      return max(rmq1[i][k],rmq1[j-(1<<k)+1][k])-min(rmq2[i][k],rmq2[j-(1<<k)+1][k]);
            33 }
            34 int main()
            35 {
            36     int i,j,k;
            37     scanf("%d%d",&N,&Q);
            38     for(i=1;i<=N;i++)
            39     {
            40         scanf("%d",&a[i]);
            41         rmq1[i][0]=a[i]; 
            42         rmq2[i][0]=a[i];                                                  //初始化
            43     }
            44     DP(N);
            45     while(Q--)
            46     {
            47         scanf("%d%d",&i,&j);
            48         printf("%d\n",search(i,j));
            49     }
            50 }
            51 

            posted on 2010-04-25 23:12 M.J 閱讀(1536) 評論(2)  編輯 收藏 引用

            評論

            # re: POJ 2762. Balanced Lineup (區(qū)間求最值sparsetable算法)  回復(fù)  更多評論   

            算法基于倍增的思想。 以空間換取時(shí)間的典范(空間開銷O(nlogn))。
            擴(kuò)展閱讀: LCA與RMQ的相互轉(zhuǎn)換等。
            2010-04-28 22:45 | Ocean

            # re: POJ 2762. Balanced Lineup (區(qū)間求最值sparsetable算法)  回復(fù)  更多評論   

            謝謝指點(diǎn)~@Ocean
            2010-04-29 16:41 | M.J

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            国产综合成人久久大片91| 久久99精品国产麻豆宅宅| 国产99久久久国产精免费| 久久久精品免费国产四虎| 精品国产婷婷久久久| 性高湖久久久久久久久AAAAA| 老男人久久青草av高清| 久久99国产精品一区二区| 一本一道久久a久久精品综合| 久久天堂AV综合合色蜜桃网| 免费一级欧美大片久久网| 精品久久久久久久无码| 久久国产影院| 69久久精品无码一区二区| 老男人久久青草av高清| 久久国产一片免费观看| 久久久久四虎国产精品| 亚洲国产欧洲综合997久久| 久久婷婷五月综合成人D啪| jizzjizz国产精品久久| 人妻无码精品久久亚瑟影视| 国产亚洲精午夜久久久久久| 久久96国产精品久久久| 久久久精品人妻一区二区三区四 | 久久久久人妻一区精品果冻| 久久国产精品一国产精品金尊| 久久国产精品无| 日韩美女18网站久久精品| 品成人欧美大片久久国产欧美| 国产情侣久久久久aⅴ免费| 无码伊人66久久大杳蕉网站谷歌| 欧美久久久久久精选9999| 国产成人无码精品久久久久免费 | 亚洲国产精品久久电影欧美| 久久久99精品成人片中文字幕| 99久久婷婷免费国产综合精品| 久久99国内精品自在现线| 久久精品国产精品亚洲毛片 | 久久精品国产72国产精福利| 伊人久久综合热线大杳蕉下载| 久久99免费视频|