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

            久久亚洲欧美国产精品| 国产激情久久久久影院老熟女免费| 久久久无码人妻精品无码| 欧美丰满熟妇BBB久久久| 久久精品国产免费观看三人同眠| 久久综合久久性久99毛片| 三级韩国一区久久二区综合 | 久久这里有精品视频| 国产精品久久精品| www.久久热.com| 激情久久久久久久久久| 久久人做人爽一区二区三区| 青草国产精品久久久久久| 91精品国产高清久久久久久91 | 久久久久夜夜夜精品国产| 91久久香蕉国产熟女线看| 精品久久久久久久久免费影院| 久久久久亚洲AV片无码下载蜜桃| 香蕉久久夜色精品国产小说| 久久婷婷五月综合色奶水99啪| 精品久久久久久久| 国内精品久久久久久久久电影网| 青青草原综合久久| 亚洲国产欧洲综合997久久| 精品一久久香蕉国产线看播放| 亚洲精品乱码久久久久久中文字幕| 久久久久成人精品无码| 97久久超碰成人精品网站| 狠狠综合久久AV一区二区三区| 精品久久久久久无码中文字幕| avtt天堂网久久精品| 久久综合九色综合网站| 免费精品久久久久久中文字幕| 2021国产成人精品久久| 久久久无码人妻精品无码| 一本久久a久久精品vr综合| 久久婷婷人人澡人人| 久久久无码精品午夜| 精品久久综合1区2区3区激情 | 久久久久久国产精品美女| 国产精品久久国产精品99盘 |