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

            久久综合精品国产一区二区三区| 国产精品欧美亚洲韩国日本久久| av色综合久久天堂av色综合在| 久久精品国产亚洲AV影院| 久久天天躁狠狠躁夜夜躁2O2O| 久久777国产线看观看精品| 国产成人精品久久| 久久精品国产99久久久古代| 国产美女久久精品香蕉69| 久久久WWW免费人成精品| 无码人妻精品一区二区三区久久 | 国产69精品久久久久777| 久久精品这里只有精99品| 奇米综合四色77777久久| 精品无码久久久久久久动漫| 久久久久亚洲AV无码麻豆| 久久久久国产精品嫩草影院| 精品久久久久久国产潘金莲| 色综合久久中文字幕综合网| 91精品国产91久久久久久蜜臀| 一级女性全黄久久生活片免费 | 国产亚洲美女精品久久久2020| 青青草国产精品久久| 欧洲精品久久久av无码电影| 欧美成人免费观看久久| 久久国产精品一区| 狠狠干狠狠久久| 久久久久亚洲AV无码永不| 嫩草伊人久久精品少妇AV| 免费久久人人爽人人爽av| 亚洲欧美国产精品专区久久| 久久久久国产一区二区| 精品国产热久久久福利| 99久久婷婷国产一区二区| 精品熟女少妇av免费久久| 久久久久无码精品国产不卡| 午夜精品久久久久久99热| 无遮挡粉嫩小泬久久久久久久| 亚洲av成人无码久久精品| 久久婷婷五月综合97色| 粉嫩小泬无遮挡久久久久久|