• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217949
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Post Office
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:1047 Accepted:456

            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

            Source
            IOI 2000

            #include? < iostream >
            using ? namespace ?std;

            /*
            p表示i到j的建一個郵局的最小值
            q表示前i個地點建j個郵局的最小值?
            dp方程

            ?????????????????p[1][i]???????????????(j?==?1)
            ?q[i][j]?=?{????????????????????????????????????????????????????}
            ????????????????q[k][j-1]?+?p[k+1][i]??(j?>?1)?(k從j-1到i-1)

            */
            ?

            int ?p[ 301 ][ 301 ];
            int ?q[ 301 ][ 31 ];
            int ?a[ 301 ];

            int ?main()
            {
            ????
            int ?V,?P;
            ????
            int ?i,?j,?k,?l;
            ????
            int ?t[ 301 ];
            ????
            int ?tmp;
            ????scanf(
            " %d%d " ,? & V,? & P);
            ????
            ????
            for ?(i = 1 ;?i <= V;?i ++ )
            ????????scanf(
            " %d " ,? & a[i]);
            ????
            ????
            for ?(i = 1 ;?i <= V;?i ++ )
            ????????
            for ?(j = i;?j <= V;?j ++ )
            ????????
            {
            ????????????
            if ?(i? == ?j)
            ????????????????p[i][j]?
            = ? 0 ;
            ????????????
            else
            ????????????
            {
            ????????????????l?
            = ?(i? + ?j)? / ? 2 ;
            ????????????????p[i][j]?
            = ? 0 ;
            ????????????????
            for ?(k = i;?k <= l;?k ++ )
            ????????????????????p[i][j]?
            += ?a[l]? - ?a[k];
            ????????????????
            for ?(k = l + 1 ;?k <= j;?k ++ )
            ????????????????????p[i][j]?
            += ?a[k]? - ?a[l];
            ???????????????
            ????????????}

            ????????}

            ????????
            ????memset(q,?
            0 ,? sizeof (q));
            ????
            for ?(i = 1 ;?i <= V;?i ++ )
            ????????
            for ?(j = 1 ;?j <= P;?j ++ )
            ????????
            {
            ????????????
            if ?(j? == ? 1 )
            ????????????????q[i][j]?
            = ?p[ 1 ][i];
            ????????????
            else
            ????????????
            {
            ????????????????
            if ?(i? >= ?j)
            ????????????????
            {
            ????????????????????q[i][j]?
            = ?q[j - 1 ][j - 1 ]? + ?p[j][i];
            ????????????????????
            for ?(k = j;?k < i;?k ++ )
            ????????????????????
            {
            ????????????????????????
            if ?(q[i][j]? > ?q[k][j - 1 ]? + ?p[k + 1 ][i])
            ????????????????????????????q[i][j]?
            = ?q[k][j - 1 ]? + ?p[k + 1 ][i];
            ????????????????????}

            ????????????????}

            ????????????}

            ????????}

            ????????
            ????cout?
            << ?q[V][P]? << ?endl;
            ????system(
            " pause " );
            ????
            return ? 0 ;
            }

            posted on 2006-09-01 22:33 閱讀(451) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            亚洲精品无码久久久久久| 亚洲国产美女精品久久久久∴| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 欧美日韩精品久久久久| 久久国产精品一区| 思思久久99热只有频精品66| 久久99久久99精品免视看动漫| 久久精品国产AV一区二区三区| 久久精品国产清高在天天线| 久久久久中文字幕| 亚洲国产高清精品线久久 | 亚洲综合久久久| 婷婷综合久久中文字幕蜜桃三电影| 国产成人久久精品激情| 久久久久97国产精华液好用吗| 亚洲国产精品无码久久| 91精品日韩人妻无码久久不卡| 亚洲精品无码久久久| 无码久久精品国产亚洲Av影片| 久久亚洲国产精品一区二区| 伊人情人综合成人久久网小说| 国产成人精品久久二区二区| 一本久久a久久精品综合香蕉| 无码人妻少妇久久中文字幕蜜桃 | 久久综合精品国产一区二区三区 | 中文字幕久久久久人妻| 国产99久久久久久免费看| 中文字幕久久精品无码| 久久亚洲av无码精品浪潮| 国产成人无码久久久精品一| 久久久SS麻豆欧美国产日韩| 久久av免费天堂小草播放| 久久国产精品无码HDAV| 国产精品乱码久久久久久软件| 亚洲国产成人久久精品影视| 久久久久久亚洲AV无码专区| 亚洲欧美另类日本久久国产真实乱对白| 国产产无码乱码精品久久鸭| 亚洲级αV无码毛片久久精品| 思思久久精品在热线热| 亚洲国产天堂久久综合|