題目 1891:
藍(lán)橋杯算法提高VIP-Trade on Verweggistan
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 6 解決: 0
題目描述
自從Peter Stuyvesant和Abel Tasman的日子以后，荷蘭商人已經(jīng)周游世界來買賣商品。有一次在Verweggistan的貿(mào)易，但是它在很短的時(shí)間后就結(jié)束了。在讀完這個(gè)故事之后你就明白了。
在當(dāng)時(shí)Verweggistan是非常受歡迎的，因?yàn)槭澜缟现挥心莻€(gè)地方的人知道怎樣制作一個(gè)“prul”（或者“prullen”，荷蘭語中的復(fù)數(shù)形式），并且如今只有很少的人知道什么是一個(gè)“prul”。
“prul”是在工場里生產(chǎn)的。當(dāng)一個(gè)“prul”做完的時(shí)候，它被包裝在一個(gè)箱子里，然后放在之前生產(chǎn)的“prul”所裝的箱子堆的上面。
價(jià)格取決于生產(chǎn)“prul”所需要的時(shí)間。如果一切順利，一個(gè)“prul”的價(jià)格會(huì)是1或者2弗羅林，但是在一個(gè)惡劣的日子，價(jià)格會(huì)很容易地上升到15弗羅林或者更高?！皃rul”在品質(zhì)上沒有什么差別，所有的“prul”具有相同的價(jià)值。
在這些天，“prul”在荷蘭的售價(jià)為每件10弗羅林。交通運(yùn)輸?shù)馁M(fèi)用是可以忽略的，因?yàn)椤皃rul”無論如何都會(huì)作為額外的東西被裝載到要航行的船上。當(dāng)一個(gè)荷蘭商人去Verweggistan時(shí)，他有一個(gè)明確的目的：買“prul”，在荷蘭銷售，并且最大化他的利潤。不幸的是，Verweggistan地區(qū)對“prul”的交易方式使得這比某些人預(yù)想的更為復(fù)雜。
有人認(rèn)為這很簡單，商人會(huì)買那些最便宜的“prul”，而那些售價(jià)比10弗羅林高的“prul”會(huì)一直不能出售。不幸的是，Verweggistan的所有工場按照一種奇怪的順序銷售“prul”。堆頂?shù)南渥永锏摹皃rul”會(huì)最先銷售，然后銷售從頂上開始數(shù)的第二個(gè)箱子里的“prul”，以此類推。所以即使第五個(gè)箱子里的“prul”是最便宜的，商人也必須買它上面四個(gè)箱子里的“prul”才能得到它。
正如你想象的那樣，這使得商人通過購買正確的“prul”的組合來最大化他們的利潤是相當(dāng)難的。沒有電腦幫助他們的優(yōu)化，他們迅速徹底失去了交易“prul”的興趣。
在這個(gè)問題中，給你對幾個(gè)工場里箱子堆的描述。你必須根據(jù)上面所給的限制，計(jì)算出一個(gè)商人通過購買箱子堆中的“prul”可以獲得的最大利潤。另外，你必須確定他需要買多少個(gè)“prul”才能獲得最大利潤。
輸入格式
輸入文件包含多組測試數(shù)據(jù)。每個(gè)測試數(shù)據(jù)的第一行是一個(gè)整數(shù)w(1<=w<=50)，該測試數(shù)據(jù)中工場的數(shù)目。
接下來有w行，每行描述一個(gè)放“prul”的箱子堆。每行的第一個(gè)整數(shù)b(0<=b<=20)，表示堆中的箱子數(shù)。接下來是b個(gè)正整數(shù)，表示堆中“prul”的價(jià)格（單位為弗羅林）。輸入中箱子的順序是從頂?shù)降住?/span>
輸入數(shù)據(jù)終止于w=0，不再有后續(xù)的描述內(nèi)容。
輸出格式
對于每組測試數(shù)據(jù)，輸出測試點(diǎn)的編號(hào)(1,2...)。然后輸出兩行，第一行輸出商人可以獲得的最大利潤。第二行輸出為獲得最大利潤商人需要買的“prul”數(shù)量。如果這個(gè)數(shù)量不是唯一確定的，按照升序輸出可能的值。如果有超過10種可能的取值，只輸出10個(gè)最小的取值。
樣例輸入
1
6 12 3 10 7 16 5
2
5 7 3 11 9 10
9 1 2 3 4 10 16 10 4 16
0
樣例輸出
Workyards 1
Maximum profit is 8.
Number of pruls to buy: 4
Workyards 2
Maximum profit is 40.
Number of pruls to buy: 6 7 8 9 10 12 13
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽