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

            coreBugZJ

            此 blog 已棄。

            Selling Land,nwerc2010 G

            Selling Land
            As you may know, the country of Absurdistan is full of abnormalities. For example, the whole
            country can be divided into unit squares that are either grass or swamp. Also, the country
            is famous for its incapable bureaucrats. If you want to buy a piece of land (called a parcel),
            you can only buy a rectangular area, because they cannot handle other shapes. The price of
            the parcel is determined by them and is proportional to the perimeter of the parcel, since the
            bureaucrats are unable to multiply integers and thus cannot calculate the area of the parcel.

                Per owns a parcel in Absurdistan surrounded by swamp and he wants to sell it, possibly in
            parts, to some buyers. When he sells a rectangular part of his land, he is obliged to announce
            this to the local bureaucrats. They will first tell him the price he is supposed to sell it for. Then
            they will write down the name of the new owner and the coordinates of the south-east corner
            of the parcel being sold. If somebody else already owns a parcel with a south-east corner at
            the same spot, the bureaucrats will deny the change of ownership.

                Per realizes that he can easily trick the system. He can sell overlapping areas, because
            bureaucrats only check whether the south-east corners are identical. However, nobody wants
            to buy a parcel containing swamp.

                In this example, dark squares represent swamp. Per may, for example, sell three overlapping grey
            areas, with dimensions 2 × 1, 2 × 4 and 4 × 1 respectively. The total perimeter is 6 + 12 + 10 = 28.
            Note that he can get more money by selling even more land. This figure corresponds to the case in
            the sample input.

                Now Per would like to know how many parcels of each perimeter he needs to sell in order
            to maximize his profit. Can you help him? You may assume that he can always find a buyer
            for each piece of land, as long as it doesn’t contain any swamps. Also, Per is sure that no
            square within his parcel is owned by somebody else.

            Input
            On the first line a positive integer: the number of test cases, at most 100. After that per test
            case:
            • One line with two integers n and m (1 ≤ n, m ≤ 1 000): the dimensions of Per’s parcel.
            • n lines, each with m characters. Each character is either ‘#’ or ‘.’. The j-th character
            on the i-th line is a ‘#’ if position (i, j) is a swamp, and ‘.’ if it is grass. The north-west
            corner of Per’s parcel has coordinates (1, 1), and the south-east corner has coordinates
            (n, m).

            Output
            Per test case:
            • Zero or more lines containing a complete list of how many parcels of each perimeter
            Per needs to sell in order to maximize his profit. More specifically, if Per should sell pi
            parcels of perimeter i in the optimal solution, output a single line “pi x i”. The lines
            should be sorted in increasing order of i. No two lines should have the same value of i,
            and you should not output lines with pi = 0.

            Sample in- and output

            Input
            1
            6 5
            ..#.#
            .#...
            #..##
            ...#.
            #....
            #..#.

            Output
            6 x 4
            5 x 6
            5 x 8
            3 x 10
            1 x 12


            比賽時就有思路,可惜時間不夠了,最后階段在沖刺另一題——可惜也是賽后幾分鐘才解決。。。


             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 #define  L  1009
             5 #define  T  (L*4)
             6 
             7 int n, m, cant[ L ][ L ], width[ L ][ L ], height[ L ][ L ];
             8 
             9 void input() {
            10         int i, j;
            11         char  tmp[ L ];
            12         scanf( "%d%d"&n, &m );
            13         gets( tmp );
            14         for ( i = 1; i <= n; ++i ) {
            15                 gets( tmp );
            16                 for ( j = 0; j < m; ++j ) {
            17                         cant[ i ][ j+1 ] = ( tmp[ j ] == '#' );
            18                 }
            19         }
            20 }
            21 
            22 void solve() {
            23         int i, j, k, most, up[ L ], left[ L ], right[ L ];
            24         memset( width, 0sizeof(width) );
            25         memset( height, 0sizeof(height) );
            26         for ( j = 1; j <= m; ++j ) {
            27                 up[ j ] = 1;
            28                 left[ j ] = 1;
            29                 right[ j ] = m;
            30         }
            31         for ( i = 1; i <= n; ++i ) {
            32                 most = 1;
            33                 for ( j = 1; j <= m; ++j ) {
            34                         if ( cant[ i ][ j ] ) {
            35                                 up[ j ] = i + 1;
            36                                 left[ j ] = 1;
            37                                 most = j + 1;
            38                         }
            39                         else if ( most > left[ j ] ) {
            40                                 left[ j ] = most;
            41                         }
            42                 }
            43 
            44                 most = m;
            45                 for ( j = m; j >= 1--j ) {
            46                         if ( cant[ i ][ j ] ) {
            47                                 most = j - 1;
            48                                 right[ j ] = m;
            49                         }
            50                         else if ( right[ j ] > most ) {
            51                                 right[ j ] = most;
            52                         }
            53                 }
            54 
            55                 up[ 0 ] = up[ 1 ] - 1;
            56                 for ( j = 1; j <= m; ++j ) {
            57                         if ( ( cant[ i ][ j ] ) || ( up[ j ] == up[ j - 1 ] ) ) {
            58                                 continue;
            59                         }
            60                         for ( k = left[ j ]; k <= right[ j ]; ++k ) {
            61                                 if ( (k-left[j]+1+ (i-up[j]+1> width[i][k] + height[i][k] ) {
            62                                         width[ i ][ k ] = k - left[ j ] + 1;
            63                                         height[ i ][ k ] = i - up[ j ] + 1;
            64                                 }
            65                         }
            66                 }
            67         }
            68 }
            69 
            70 void output() {
            71         int cnt[ T ], i, j;
            72         memset( cnt, 0sizeof(cnt) );
            73         for ( i = 1; i <= n; ++i ) {
            74                 for ( j = 1; j <= m; ++j ) {
            75                         ++cnt[ ( width[i][j] + height[i][j] ) << 1 ];
            76                 }
            77         }
            78         for ( i = 1; i < T; ++i ) {
            79                 if ( cnt[ i ] > 0 ) {
            80                         printf( "%d x %d\n", cnt[ i ], i );
            81                 }
            82         }
            83 }
            84 
            85 int main() {
            86         int td;
            87         scanf( "%d"&td );
            88         while ( td-- > 0 ) {
            89                 input();
            90                 solve();
            91                 output();
            92         }
            93         return 0;
            94 }
            95 

            posted on 2011-04-29 21:05 coreBugZJ 閱讀(378) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            99国产欧美久久久精品蜜芽| 国产精品99精品久久免费| 亚洲狠狠综合久久| 久久亚洲精品无码播放| 久久久这里只有精品加勒比| 性欧美丰满熟妇XXXX性久久久 | 久久伊人五月丁香狠狠色| 狠狠色婷婷久久综合频道日韩| 久久久久高潮毛片免费全部播放| 精品多毛少妇人妻AV免费久久| 亚洲第一永久AV网站久久精品男人的天堂AV | 成人午夜精品久久久久久久小说 | 精品综合久久久久久888蜜芽| 办公室久久精品| 国产午夜福利精品久久2021 | 婷婷久久综合| 91久久九九无码成人网站| 伊人久久精品无码二区麻豆| 久久无码精品一区二区三区| 久久91精品国产91久久户| 久久精品国产亚洲AV蜜臀色欲 | 精品无码久久久久国产动漫3d| 久久久久久亚洲精品不卡 | 久久亚洲国产精品123区| 狠狠色婷婷综合天天久久丁香 | 日韩av无码久久精品免费| 亚洲欧美精品一区久久中文字幕| 久久91亚洲人成电影网站| 亚洲伊人久久大香线蕉综合图片| 久久中文字幕精品| 欧美伊人久久大香线蕉综合69| 国产成人无码精品久久久免费| 99国产精品久久| 国产一区二区三区久久精品| 99久久99久久| 久久亚洲精品视频| 亚洲一本综合久久| 99久久精品国产毛片| 久久国产视屏| 一个色综合久久| 亚洲精品乱码久久久久久蜜桃不卡 |