• <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 已棄。

            POJ 1160 Post Office

            POJ 1160 Post Office
            Time Limit: 1000MS
            Memory Limit: 10000K
            Total Submissions: 10151
            Accepted: 5466

            Description

            There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.

            Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.

            You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

            Input

            Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000.

            Output

            The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.

            Sample Input

            10 5
            1 2 3 6 7 9 11 22 44 50

            Sample Output

            9



            我的代碼 :

            簡單的 DP,未使用四邊形不等式優化 :

            #include <stdio.h>
            #include 
            <string.h>

            #define  N  309
            #define  M  39

            int n, m, x[ N ];

            int solve() {
                    
            int i, j, k, f[ N ][ M ], w[ N ][ N ], tmp;
                    
            int OO = 0x3f3f3f3f;

                    
            int t[ N ];
                    t[ 
            0 ] = 0;
                    
            for ( i = 1; i <= n; ++i ) {
                            t[ i ] 
            = t[ i - 1 ] + x[ i ];
                    }
                    
            for ( i = 1; i <= n; ++i ) {
                            w[ i ][ i ] 
            = 0;
                            
            for ( j = i + 1; j <= n; ++j ) {
                                    k 
            = ( j - i ) / 2 + i;
                                    w[ i ][ j ] 
            = t[ j ] - t[ k ] - t[ k - 1 ] + t[ i - 1 ] + x[ k ] * ( k + k - i - j );
                            }
                    }

                    memset( f, 
            0x3fsizeof(f) );
                    f[ 
            0 ][ 0 ] = 0;
                    
            for ( i = 1; i <= n; ++i ) {
                            
            for ( j = 1; j <= m; ++j ) {
                                    
            for ( k = 0; k < i; ++k ) {
                                            
            if ( f[ k ][ j - 1 ] != OO ) {
                                                    tmp 
            = f[ k ][ j - 1 ] + w[ k + 1 ][ i ];
                                                    
            if ( tmp < f[ i ][ j ] ) {
                                                            f[ i ][ j ] 
            = tmp;
                                                    }
                                            }
                                    }
                            }
                    }
                    
            return f[ n ][ m ];
            }

            int main() {
                    
            int i;
                    scanf( 
            "%d%d"&n, &m );
                    
            for ( i = 1; i <= n; ++i ) {
                            scanf( 
            "%d", x + i );
                    }
                    printf( 
            "%d\n", solve() );
                    
            return 0;
            }

            posted on 2011-03-17 18:59 coreBugZJ 閱讀(1347) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久伊人精品一区二区三区| 国产午夜精品久久久久九九| 久久精品国产一区二区三区| 久久九九久精品国产免费直播| 久久久久无码国产精品不卡| 青青草原综合久久大伊人| 99re久久精品国产首页2020| 久久99精品久久久久久水蜜桃| 伊人色综合久久天天网| 精品久久久久久国产| 精品国产日韩久久亚洲| 久久这里只有精品久久| 囯产精品久久久久久久久蜜桃 | 久久久这里只有精品加勒比| 国产成年无码久久久久毛片| 日韩欧美亚洲国产精品字幕久久久| 精品久久久久久国产| 久久久久亚洲AV无码专区桃色| 久久亚洲精品成人AV| 午夜视频久久久久一区 | 色青青草原桃花久久综合| 久久亚洲国产午夜精品理论片| 国产亚洲精品久久久久秋霞| 日韩久久久久中文字幕人妻| 国产午夜精品久久久久九九| 国产A级毛片久久久精品毛片| 久久综合综合久久综合| 久久AV无码精品人妻糸列| 欧洲国产伦久久久久久久 | 久久99久久无码毛片一区二区| 精品无码久久久久国产| 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 | 国产精品久久久久jk制服| 亚洲精品乱码久久久久久按摩| 青青青青久久精品国产h久久精品五福影院1421 | 精品人妻久久久久久888| 天堂久久天堂AV色综合| 久久婷婷国产综合精品| 无码人妻久久一区二区三区| 久久国产劲爆AV内射—百度| 亚洲va国产va天堂va久久|