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

            国产精品VIDEOSSEX久久发布| 伊人情人综合成人久久网小说| 亚洲色婷婷综合久久| 99久久国产宗和精品1上映| 久久久亚洲欧洲日产国码aⅴ| 日韩精品国产自在久久现线拍| 日本久久久久久久久久| 久久精品无码一区二区无码| 久久久久久一区国产精品| 一本一本久久A久久综合精品 | 人妻中文久久久久| 欧美黑人激情性久久| 久久五月精品中文字幕| 日韩人妻无码精品久久免费一 | 久久天堂电影网| 久久精品国产色蜜蜜麻豆| 久久精品亚洲福利| 久久精品九九亚洲精品| 超级97碰碰碰碰久久久久最新| 久久精品成人免费看| 色88久久久久高潮综合影院| 亚洲国产成人精品无码久久久久久综合| 日产精品久久久久久久性色| 欧美一区二区久久精品| 国产A级毛片久久久精品毛片| 精品久久久久久无码专区| 精品国产乱码久久久久久呢| 青青青青久久精品国产h久久精品五福影院1421 | 中文字幕精品久久| 久久久久亚洲AV无码专区桃色| 亚洲国产精品久久久久网站| 久久精品国产清自在天天线| 欧美黑人激情性久久| 午夜精品久久久久9999高清| 久久久久97国产精华液好用吗| 青青青青久久精品国产h| 久久er热视频在这里精品| 久久夜色精品国产网站| 久久人人爽爽爽人久久久| 久久发布国产伦子伦精品| 国产精品久久99|