• <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>

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2019 Cornfields 動態規劃

            題目大意:
            給出一個N*N的矩陣,要查詢任意B*B子矩陣內的元素最大值和最小值之差。

            思路:
            這應該算是一個二維的 RMQ 問題。但是做之前還不知道有RMQ這回事,就用一個動態規劃做了。
            還好速度也慢不到哪里去,也過了。哈哈。

            #include <stdio.h>

            struct node {
                unsigned 
            char arr[254], max, min;
            }
            ;

            __inline 
            void node_init(struct node *n)
            {
                n
            ->max = 0;
                n
            ->min = 255;
            }


            __inline 
            void node_add(struct node *n, unsigned char val)
            {
                n
            ->arr[val]++;
                
            if (val > n->max)
                    n
            ->max = val;
                
            if (val < n->min)
                    n
            ->min = val;
            }


            __inline 
            void node_del(struct node *n, unsigned char val)
            {
                n
            ->arr[val]--;
                
            while (!n->arr[n->max])
                    n
            ->max--;
                
            while (!n->arr[n->min])
                    n
            ->min++;
            }


            int N, B, K;
            unsigned 
            char data[256][256];
            struct node row[256], col[256];
            unsigned 
            char ans[256][256];

            int main()
            {
                
            int i, j, k;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d%d"&N, &B, &K);
                
            for (i = 0; i < N; i++{
                    
            for (j = 0; j < N; j++{
                        scanf(
            "%d"&k);
                        data[i][j] 
            = k;
                    }

                }


                
            for (i = 0; i < N; i++{
                    node_init(
            &row[i]);
                    
            for (j = 0; j < B; j++)
                        node_add(
            &row[i], data[i][j]);
                }

                
            for (i = 0; ; i++{
                    node_init(
            &col[i]);
                    
            for (j = 0; j < B; j++{
                        node_add(
            &col[i], row[j].max);
                        node_add(
            &col[i], row[j].min);
                    }

                    
            while (1{
                        ans[j 
            - B][i] = col[i].max - col[i].min;
                        
            if (j == N)
                            
            break;
                        node_del(
            &col[i], row[j - B].max);
                        node_del(
            &col[i], row[j - B].min);
                        node_add(
            &col[i], row[j].max);
                        node_add(
            &col[i], row[j].min);
                        j
            ++;
                    }

                    
            if (i == N - B)
                        
            break;
                    
            for (j = 0; j < N; j++{
                        node_del(
            &row[j], data[j][i]);
                        node_add(
            &row[j], data[j][i + B]);
                    }

                }


                
            while (K--{
                    scanf(
            "%d%d"&i, &j);
                    printf(
            "%d\n", ans[i - 1][j - 1]);
                }


                
            return 0;
            }

            posted on 2010-03-03 14:50 糯米 閱讀(681) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久香蕉国产线看观看精品yw| 久久人与动人物a级毛片| 伊人久久大香线蕉影院95| 久久精品国产亚洲5555| 中文字幕日本人妻久久久免费| 久久精品国产精品国产精品污| 久久伊人亚洲AV无码网站| www.久久精品| 久久精品亚洲AV久久久无码| 四虎国产精品免费久久5151| 中文字幕无码久久久| 91麻精品国产91久久久久| 亚洲精品美女久久777777| 亚洲国产小视频精品久久久三级| 国产精品一久久香蕉国产线看观看| 久久久WWW成人免费精品| 久久久一本精品99久久精品88| 一级a性色生活片久久无| 嫩草影院久久99| 2021久久国自产拍精品| 少妇久久久久久被弄高潮| 亚洲精品无码久久不卡| 国产精品美女久久久免费| 成人妇女免费播放久久久| 国内精品人妻无码久久久影院导航| 久久精品国产国产精品四凭| 99久久国产综合精品网成人影院| 精品久久久久久无码专区不卡| 国产亚洲美女精品久久久2020| 久久久久人妻一区二区三区| 久久久久亚洲爆乳少妇无| 国产巨作麻豆欧美亚洲综合久久| 久久亚洲精品中文字幕三区| 一本久久久久久久| 国产高潮久久免费观看| 国产精品美女久久久久av爽| 久久精品无码免费不卡| 亚洲v国产v天堂a无码久久| 久久午夜福利无码1000合集| 一本一本久久a久久综合精品蜜桃| 中文字幕乱码人妻无码久久|