青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

POJ 1505 Copying Books 動態規劃

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

     

    假設有M本書(編號為12M),想將每本復制一份,M本書的頁數可能不同(分別是P1P2PM)。任務時將這M本書分給K個抄寫員(KM〉,每本書只能分配給一個抄寫員進行復制,而每個抄寫員所分配到的書必須是連續順序的。

    意思是說,存在一個連續升序數列0=b0b1b2bk-1bk=m,這樣,第i號抄寫員得到的書稿是從bi-1+1到第bi本書。復制工作是同時開始進行的,并且每個抄寫員復制的速度都是一樣的。所以,復制完所有書稿所需時間取決于分配得到最多工作的那個抄寫員的復制時間。試找一個最優分配方案,使分配給每一個抄寫員的頁數的最大值盡可能小(如存在多個最優方案,只輸出其中一種)。
    設dp[i,j]表示前j個人復制前i本書所需要的最少時間,有狀態轉移方程dp[i,j]=min(dp[i,j],max(dp[v,j-1],sum[v+1,i])),其中1<=i<=m,1<=j<=k,j-1<=v<=i-1,sum[v+1,j]表示第v+1本書到第i本書的頁數之和。

#include<iostream>
using namespace std;

const int MAXN = 510;
int sum[MAXN],path[MAXN],dp[MAXN][MAXN];

int main(){
    
int m,k,i,j,v,ca,p,t;
    scanf(
"%d",&ca);
    
while(ca--){
        scanf(
"%d %d",&m,&k);
        
for(sum[0]=0,i=1;i<=m;i++){
            scanf(
"%d",&p);
            sum[i]
=sum[i-1]+p;
        }

        memset(dp,
-1,sizeof(dp));
        
for(dp[0][0]=0,i=1;i<=m;i++)
            
for(j=1;j<=&& j<=k;j++){
                
if(j==1) dp[i][j]=sum[i];
                
else
                    
for(v=j-1;v<=i-1;v++){
                        t
=max(dp[v][j-1],sum[i]-sum[v]);
                        
if(dp[i][j]==-1 || t<=dp[i][j]) 
                            dp[i][j]
=t;
                    }

            }

        
for(i=m,j=k-1,p=0;i>=1;i--){
            p
+=sum[i]-sum[i-1];
            
if(p>dp[m][k] || i<=j){
                path[j
--]=i+1;
                p
=sum[i]-sum[i-1];
            }

        }

        
for(i=j=1;i<=m;i++){
            
if(i>1) printf(" ");
            
if(j<&& path[j]==i){
                printf(
"");
                j
++;
            }

            printf(
"%d",sum[i]-sum[i-1]);
        }

        printf(
"\n");
    }

    
return 0;
}

posted on 2009-06-16 09:59 極限定律 閱讀(3629) 評論(12)  編輯 收藏 引用 所屬分類: ACM/ICPC

評論

# re: POJ 1505 Copying Books 動態規劃 2009-06-16 22:30 bafangprinter

China-Beijing bafang printing plant,Offers business printing services ,Full colour printing service for brochures,paper bag,newsletters,magazines,catalogues,Boxprinting,Paper processing,Drugs ,Business Cards, Box,Jewel box,Gift box,Kraft paper bags,Corrugated Box,Beijing Printing, Foreigners in China ,All are welcome to the Advisory order! TEL:86-010-51665543 MSN:beijingbafang@hotmail.com http://www.print861.com Fengtai District Beijing  China   回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2009-11-17 22:21 Gamor

二分最大值也可以過。  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2010-07-18 19:33 AnnetteKRAMER

I would like to propose not to hold back until you get enough amount of cash to buy different goods! You can just get the <a href="http://bestfinance-blog.com/topics/personal-loans">personal loans</a> or just secured loan and feel yourself comfortable   回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2010-08-02 17:01 buy essay

Study process demands creative writing skills, nevertheless, college students, which don't have time can fail their academic career. Hence, to purchase the term papers from the buy term paper service would be a right decision.   回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2010-08-05 16:36 term paper

This is what I was exploring for a long time! Thanks for this article around university! One time somebody state that In union there is effect. Our powerfully skilled service can help you in writing custom research papers.  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2010-08-11 20:30 essay writing service

Do you work a lot on your writing assignment? You do not have to bother about that any longer, because you can buy essay papers.   回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃[未登錄] 2010-09-25 11:15 dress

Best canon Coffee Mugs! Funny, Cute, & Humorous Unique designs. Also find Travel Mugs, Coffee Cups also, or Create Photo Personalized Mugs & Drinkware  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2012-02-11 12:45 resume writing

The article you post by scribers is very interesting, now we understand how xerox copy machine came to being, its a great info.  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2012-04-17 16:09 help in writing term papers

This article defines how things came to being,here i found so many information related to copying books and machines.Its nice to read this book.  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃[未登錄] 2013-05-12 19:40 BETTY

格式有點囧  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2013-06-17 20:01 this site

Go to Perfect-resume company (perfect-resume.com) if you are in need of reliable resume services. Having delt with this trustable agency, you will be aware of which service to choose for buying resume and where to look through samples of resume writing. Don’t mull over, buy CV of good quality from expert resume writers.  回復  更多評論   

# re: POJ 1505 Copying Books 動態規劃 2013-06-17 20:02 Internet site

Professional resume writers review will hint you where to buy resume paper if you are too busy to write a resume, just visit Resumes expert company resumesexpert.com, view resume writing samples and our certified resume writers will be ready to provide you best CV writing. Buying resume with us is pretty easy, buy resumes now and stay satisfied about your career.  回復  更多評論   

<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品久久久久久亚洲毛片| 久久人人看视频| 国产精品一区=区| 亚洲欧美日本另类| 亚洲欧美区自拍先锋| 国产亚洲免费的视频看| 久久美女性网| 欧美成人国产一区二区| 一级日韩一区在线观看| 在线一区日本视频| 国产欧美日韩视频| 欧美成人激情在线| 欧美日本不卡| 久久精品国产精品| 免费看成人av| 亚洲欧美激情在线视频| 欧美一区二区三区四区夜夜大片| 亚洲国产高潮在线观看| 亚洲美女在线国产| 国产真实久久| av成人毛片| 一区二区视频免费在线观看| 亚洲国语精品自产拍在线观看| 欧美二区不卡| 久久久99精品免费观看不卡| 欧美黄色一区| 久久亚洲国产成人| 欧美日韩三区| 欧美高清视频www夜色资源网| 欧美日韩国产一区| 快播亚洲色图| 国产精品一卡二卡| 99国产精品久久久久久久久久| 国产一区二区日韩精品| 洋洋av久久久久久久一区| 有坂深雪在线一区| 亚洲欧美www| 中国成人亚色综合网站| 久久人人97超碰精品888| 午夜精品福利视频| 欧美另类人妖| 亚洲高清不卡在线| 国内精品国产成人| 亚洲男女自偷自拍| 亚洲一区在线直播| 欧美区在线播放| 欧美激情精品久久久久久久变态| 国产视频欧美视频| 亚洲婷婷综合色高清在线| 亚洲精品美女91| 麻豆国产精品va在线观看不卡| 性做久久久久久免费观看欧美| 欧美国产在线观看| 欧美国产日韩一区二区三区| 一区在线视频| 久久精品视频一| 久久五月激情| 黑丝一区二区三区| 欧美一区亚洲二区| 久久久999成人| 国内自拍亚洲| 久久久福利视频| 久久综合给合| 亚洲第一级黄色片| 免费成人你懂的| 亚洲电影欧美电影有声小说| 亚洲日本久久| 欧美精品激情在线| 一区二区不卡在线视频 午夜欧美不卡在 | 欧美视频一区二区三区在线观看| 欧美成人国产va精品日本一级| 在线国产精品播放| 蜜桃av一区二区| 亚洲韩国精品一区| 亚洲一区二区高清| 国产欧美日韩91| 欧美专区在线观看| 欧美成人免费播放| 亚洲免费黄色| 国产精品国产三级国产专播精品人| 亚洲午夜羞羞片| 久久精品免费| 亚洲人成毛片在线播放| 欧美日本在线播放| 午夜国产精品视频| 欧美成人国产一区二区| 亚洲桃色在线一区| 国产亚洲一区在线播放| 久久在线免费视频| 一本色道久久综合狠狠躁篇的优点| 亚洲一区二区成人| 欲香欲色天天天综合和网| 欧美国产日本| 亚洲欧美激情一区二区| 亚洲国产精品高清久久久| 亚洲欧美国产77777| 激情五月婷婷综合| 欧美日韩另类综合| 久久国产主播| 99精品99久久久久久宅男| 久久精品亚洲国产奇米99| 亚洲精品视频二区| 国产精品永久免费观看| 美女日韩欧美| 午夜久久tv| 亚洲精选成人| 欧美xart系列在线观看| 午夜精品亚洲| 日韩午夜在线播放| 国产自产在线视频一区| 欧美日韩一区二区免费视频| 久久青草久久| 午夜精品久久久久久| 亚洲韩国青草视频| 免费影视亚洲| 久久久国产精品一区| 亚洲视频1区2区| 亚洲精品偷拍| 亚洲国产精品久久久久婷婷老年| 国产精品一区二区久激情瑜伽| 欧美精品日韩综合在线| 久久青草久久| 久久久一区二区| 欧美在线影院在线视频| 亚洲天堂男人| 一区二区电影免费观看| 亚洲剧情一区二区| 最新中文字幕亚洲| 欧美激情2020午夜免费观看| 久久免费视频一区| 久久精品综合| 久久成人资源| 欧美综合二区| 欧美在线视频日韩| 先锋影院在线亚洲| 午夜精品短视频| 欧美一级大片在线免费观看| 亚洲欧美日韩精品一区二区| 亚洲网友自拍| 亚洲欧美精品suv| 欧美一区三区二区在线观看| 亚洲欧美资源在线| 午夜视频精品| 久久国产精品久久久久久久久久 | 蜜桃久久精品乱码一区二区| 久久一区亚洲| 欧美电影免费观看大全| 嫩草影视亚洲| 亚洲成在人线av| 亚洲日韩欧美视频| 中文国产一区| 欧美在线观看天堂一区二区三区| 欧美一级二级三级蜜桃| 久久精品一区中文字幕| 久久综合给合久久狠狠狠97色69| 老牛国产精品一区的观看方式| 美国十次成人| 欧美精品在线观看| 欧美日韩精品一区二区三区四区| 欧美日韩一区二区三区在线视频 | 欧美理论电影在线播放| 欧美日韩亚洲天堂| 国产精品激情av在线播放| 国产区在线观看成人精品| 狠狠色丁香久久婷婷综合丁香| 在线高清一区| 99re6这里只有精品视频在线观看| 亚洲图片在线观看| 久久久久久久高潮| 亚洲国产成人精品久久| 一区二区免费在线视频| 久久精品国产第一区二区三区| 免费观看成人网| 欧美午夜视频一区二区| 精品av久久707| 亚洲色无码播放| 久久久欧美一区二区| 亚洲人成人一区二区在线观看| 亚洲中字黄色| 欧美精品二区三区四区免费看视频| 国产精品久久久久久久久久免费看| 国产一区二区三区成人欧美日韩在线观看 | 亚洲精品一级| 欧美专区一区二区三区| 欧美日韩国产天堂| 在线观看日韩国产| 亚洲欧美日韩国产中文| 欧美国产一区二区三区激情无套| 在线亚洲伦理| 欧美v日韩v国产v| 国产日韩欧美视频在线| 在线天堂一区av电影| 老司机一区二区| 亚洲欧美另类在线| 欧美日本亚洲| 亚洲国产片色| 免费不卡在线视频| 午夜精品福利视频| 欧美日韩网址| 日韩亚洲欧美精品|