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

            搜索

            •  

            積分與排名

            • 積分 - 217880
            • 排名 - 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題目
            精品久久久久久无码专区不卡| 久久精品国产男包| 青青草原1769久久免费播放| 青青青国产精品国产精品久久久久| 色综合色天天久久婷婷基地| 午夜精品久久久内射近拍高清| 久久久国产视频| 欧美精品一区二区精品久久| 欧美性大战久久久久久| 免费久久人人爽人人爽av| 午夜不卡888久久| 国产激情久久久久久熟女老人| 久久久久久久综合日本亚洲 | 人妻精品久久久久中文字幕69| 国产一级持黄大片99久久| 波多野结衣久久精品| segui久久国产精品| 狼狼综合久久久久综合网| 久久久人妻精品无码一区| 狠狠狠色丁香婷婷综合久久五月| 久久久无码精品亚洲日韩蜜臀浪潮| 久久九九亚洲精品| 久久99国产综合精品女同| 亚洲精品久久久www| 成人a毛片久久免费播放| 亚洲国产精品热久久| 久久99国产综合精品女同| 久久精品亚洲中文字幕无码麻豆| 日韩美女18网站久久精品| 久久精品无码一区二区日韩AV| 国产精品一久久香蕉产线看| 亚洲精品tv久久久久久久久| 久久精品国产亚洲AV忘忧草18| 久久亚洲高清综合| 久久精品中文字幕一区| 久久久久久毛片免费看| 久久影院久久香蕉国产线看观看| 久久久中文字幕日本| 欧美久久一区二区三区| 一级女性全黄久久生活片免费 | 伊人久久无码精品中文字幕|