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

            QuXiao

            每天進(jìn)步一點(diǎn)點(diǎn)!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks

            解題報告

             

            題目來源:

            PKU 1505 Copying Books

             

            算法分類:

            DP

             

            原文:

            Copying Books

            Time Limit: 3000MS


            Memory Limit: 10000K

            Total Submissions: 1806


            Accepted: 404

            Description

            Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

            Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

            Input

            The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.

            Output

            For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

            If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

            Sample Input

            2

            9 3

            100 200 300 400 500 600 700 800 900

            5 4

            100 100 100 100 100

            Sample Output

            100 200 300 400 500 / 600 700 / 800 900

            100 / 100 / 100 / 100 100

            Source

            Central Europe 1998

             

             

            中文描述:

            題目大意是給你m1…m)本書,每本書有Pm頁,用kk<=m)個員工來復(fù)印這些書。每本書只能分配給一個員工來復(fù)印,并且每個員工必須復(fù)印一段連續(xù)的書籍,每個員工復(fù)印的時間取決于所復(fù)印書籍的總頁數(shù)。讓你給出相應(yīng)的分配,使得分配給員工的書籍頁數(shù)的最大值盡量小。注意,如果有多種分配的方案,使得第一個員工的書籍頁數(shù)盡量少,其次是第二個、第三個……以此類推。

             

            題目分析:

            我們可以從后往前推,最后一個員工,也就是第k個員工,他至少要復(fù)印第m本書,至多可以復(fù)印第k本到第m本(因?yàn)橹辽僖峙浣o前k-1個員工每人一本書)。假設(shè),第k名員工復(fù)制第ik<=i<=m)本書到第m本書,那么,所有員工復(fù)印書籍的最小時間就為第k名員工所需的時間以及前k-1名員工復(fù)制前i-1本書所需最小時間的較大的那個時間。這樣,問題的規(guī)模就從k個員工復(fù)印m本書減小到了k-1個員工復(fù)印i-1本書,而且求解過程中會不斷遇到前a個員工復(fù)印前b本書的最小時間。為了減小問題的規(guī)模以及記錄重復(fù)子問題的解,就可以用DP

            但僅僅算出最小時間的不夠的,還要給出分配的方案,這個稍微有點(diǎn)繁瑣。因?yàn)轭}目中說,如果有多種最優(yōu)的分配方案,應(yīng)該讓前面的員工分配的頁數(shù)盡量少。那么,可以從后推,在當(dāng)前的員工所復(fù)印的書籍頁數(shù)沒有超過最大頁數(shù)的情況下,讓其復(fù)印的頁數(shù)最大化。如果超過了最大頁數(shù),就把這本書分配給前一名員工。最后再按順序?qū)⒎峙浣Y(jié)果輸出出來。

             

            代碼:

            #include <cstdio>

            #include <climits>

            #include <cstring>

             

            const int MAX = 505;

            int book[MAX];

            __int64 total[MAX];                        //1~n本書的頁數(shù)

            int k, m;

            __int64 f[MAX][MAX];                  //f[i][j] = k 表示前i個人復(fù)制前j本書所需最少時間是k

            __int64 max;

            void Input ()

            {

                            scanf("%d%d", &m, &k);

                            int i;

                            for (i=1; i<=m; i++)

                                            scanf("%d", &book[i]);

            }

             

            __int64 Sum (int s, int e)                                               //s本書到第e本書的總頁數(shù)

            {

                            return (total[e] - total[s-1]);

            }

             

            __int64 Max (__int64 a, __int64 b)

            {

                            return ( a>b?a:b );

            }

             

            __int64 Min (int x, int y)                                //x個人復(fù)制前y本書所需的最少時間        x<=y

            {

            //考慮特殊情況

                            if ( f[x][y] != -1 )

                                            return f[x][y];

                            if ( y == 0 )

                                            return ( f[x][y] = 0 );

                            if ( x == 0 )

                                            return ( f[x][y] = INT_MAX );

             

                            int i;

                            __int64 temp;

                            f[x][y] = INT_MAX;

                            for (i=x-1; i<y; i++)

                            {

            //x個人復(fù)制第i+1到第y本書與前x-1個人復(fù)制前i本書的時間較大的時間

                                            temp = Max( Min(x-1, i), Sum(i+1, y) );                 

                                            if ( temp < f[x][y] )

                                            {

                                                            f[x][y] = temp;

                                            }

                            }

                            return f[x][y];

            }

             

            void Output ()

            {

                            int i, p;

                            __int64 temp;

                            int slash[MAX];

                            max = f[k][m];

                            memset(slash, 0, sizeof(slash));

                            temp = 0;

                            p = k;

                            for (i=m; i>0; i--)

                            {

                                            //讓后面的員工盡量復(fù)印最多的書籍

                                            if ( temp + book[i] > max || i < p )

                                            {

                                                            slash[i] = 1;

                                                            temp = book[i];

                                                            p --;

                                            }

                                            else

                                            {

                                                            temp += book[i];

                                            }

                            }

             

                            for (i=1; i<=m; i++)

                            {

                                            printf("%d", book[i]);

                                            if ( slash[i] == 1 )

                                                            printf(" / ");

                                            else if ( i != m )

                                                            printf(" ");

                            }

                            printf("\n");

            }

             

            void Solve ()

            {

                            int i, j;

                            //預(yù)處理書籍頁數(shù)的和

                            total[0] = 0;

                            for (i=1; i<=m; i++)

                                            total[i] = total[i-1] + book[i];

             

                            memset(f, -1, sizeof(f));

                           

                            Min(k, m);

                           

                            Output();

            }

             

            int main ()

            {

                            int test;

                            scanf("%d", &test);

                            while ( test-- )

                            {

                                            Input ();

                                            Solve ();

                            }

             

                            return 0;

            }

             

             

            程序分析與心得:

            時間復(fù)雜度O(n2),空間復(fù)雜度O(n2)

            在用記憶化搜索解決DP問題時,往往比較符合人的思維,容易想到模型,編程比較簡單。在解題過程中,除了可以按照常理順著推,也可以嘗試逆向思維,從最后的狀態(tài)倒著推,這樣可以使問題想得更加透徹,有比較好的效果。

            posted on 2008-03-10 15:11 quxiao 閱讀(558) 評論(0)  編輯 收藏 引用 所屬分類: ACM
            色综合久久中文字幕无码| 99久久香蕉国产线看观香| 久久人人爽爽爽人久久久| 久久久久久曰本AV免费免费| 久久久久人妻一区二区三区vr| 99久久精品影院老鸭窝| 久久精品中文字幕第23页| 久久综合久久美利坚合众国| 国产欧美久久一区二区| 亚洲精品高清一二区久久| 粉嫩小泬无遮挡久久久久久| 久久中文精品无码中文字幕| 国产亚洲精久久久久久无码| 久久天天躁狠狠躁夜夜2020老熟妇| 亚洲av伊人久久综合密臀性色| 99久久综合国产精品二区| 日本欧美久久久久免费播放网 | 久久久久av无码免费网| 精品久久久久久中文字幕| 久久无码AV中文出轨人妻| 国产2021久久精品| 精品国际久久久久999波多野| 久久天天躁狠狠躁夜夜2020一| 久久美女网站免费| 国产精品无码久久久久久| 亚洲熟妇无码另类久久久| 亚洲国产精品综合久久一线| 国产成人无码精品久久久久免费| 精品综合久久久久久888蜜芽| 久久亚洲sm情趣捆绑调教| 久久一区二区三区免费| 国产精品综合久久第一页 | 亚洲国产成人久久综合区| 国产亚洲精午夜久久久久久 | 国产99久久九九精品无码| 9久久9久久精品| 99久久久国产精品免费无卡顿| 国产V综合V亚洲欧美久久| 久久精品夜夜夜夜夜久久| 久久久久亚洲Av无码专| 久久精品中文字幕久久|