• <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 閱讀(380) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            日本精品久久久久中文字幕8| AV狠狠色丁香婷婷综合久久| 精品久久久久久无码不卡| 欧美精品福利视频一区二区三区久久久精品| 亚洲国产精品久久久久久| 亚洲精品视频久久久| 久久精品九九亚洲精品天堂| 久久伊人五月天论坛| 久久国产免费观看精品3| 久久久久人妻一区精品| 婷婷伊人久久大香线蕉AV| 欧美激情精品久久久久久| 久久国产精品99国产精| 午夜精品久久久久| 欧美国产成人久久精品| 91精品国产高清久久久久久91 | 97超级碰碰碰碰久久久久| 色老头网站久久网| 91麻精品国产91久久久久| 亚洲AV无码一区东京热久久 | 要久久爱在线免费观看| 久久精品www| 国产精品99精品久久免费| 久久精品国产亚洲av麻豆蜜芽| 国内精品久久久久久中文字幕| 国产成人精品久久免费动漫| 色偷偷88888欧美精品久久久| 怡红院日本一道日本久久 | 欧美亚洲国产精品久久蜜芽| 亚洲AV日韩精品久久久久| 国产69精品久久久久APP下载| 久久93精品国产91久久综合| 亚洲成人精品久久| 亚洲午夜久久久精品影院 | 99久久无码一区人妻| 亚洲精品国产成人99久久| 岛国搬运www久久| 久久精品无码av| 狠狠色丁香久久婷婷综合_中| 一97日本道伊人久久综合影院| 久久99精品久久久大学生|