题目描述荷兰商人前往Verweggistan \texttt{Verweggistan}Verweggistan购买一种名为“prul \texttt{prul}prul”的商品。每个prul \texttt{prul}prul在荷兰售价为10 1010弗罗林。每个工作坊将生产的prul \texttt{prul}prul堆成一摞出售时必须从顶部到底部按顺序购买即若想买第k kk个必须同时买前k − 1 k-1k−1个。每个盒子标有制造成本。给定若干个工作坊的堆栈每个堆栈最多20 2020个盒子要求选择一个购买方案使得总利润最大利润 售价 - 成本。输出最大利润以及所有能实现该最大利润的购买总数即所有工作坊购买盒子数量之和。若有多个可能的总数按升序输出若超过10 1010个则只输出最小的10 1010个。输入格式输入包含多个测试用例。每个测试用例第一行为一个整数w ww1 ≤ w ≤ 50 1 \le w \le 501≤w≤50表示工作坊数量。随后w ww行每行描述一个堆栈第一个整数b bb0 ≤ b ≤ 20 0 \le b \le 200≤b≤20表示盒子数随后b bb个正整数表示从顶部到底部的成本。输入以w 0 w 0w0结束。输出格式对于每个测试用例输出Workyards k Maximum profit is maxProfit. Number of pruls to buy: list其中l i s t listlist为可能购买总数升序排列空格分隔若只有0 00个可能值输出0。每个测试用例输出后跟一个空行。样例输入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题目分析对于每个堆栈若购买前j jj个盒子1 ≤ j ≤ b 1 \le j \le b1≤j≤b利润为10 j − ∑ t 1 j c o s t t 10j - \sum_{t1}^j cost_t10j−∑t1j​costt​。记p [ j ] p[j]p[j]为该利润值p [ 0 ] 0 p[0] 0p[0]0。堆栈的最大利润为该堆栈能获得的最大利润即max ⁡ 0 ≤ j ≤ b p [ j ] \max_{0 \le j \le b} p[j]max0≤j≤b​p[j]。若最大利润为负则该堆栈不购买任何盒子利润为0 00且不参与后续计数因为购买负数利润会降低总利润。每个堆栈独立选择达到其最大利润的购买数量可能有多个。总最大利润为各堆栈最大利润之和。所有可能的购买总数为各堆栈可达到最大利润的购买数量之间的所有组合之和。解题思路实现步骤如下步骤1 \texttt{1}1. 读入w ww。对每个堆栈i ii读入b bb和b bb个成本值。计算前缀利润数组p r e f [ j ] 10 j − ∑ t 1 j c o s t t pref[j] 10j - \sum_{t1}^j cost_tpref[j]10j−∑t1j​costt​0 ≤ j ≤ b 0 \le j \le b0≤j≤b。步骤2 \texttt{2}2. 求该堆栈的最大利润m a x P max ⁡ 0 ≤ j ≤ b p r e f [ j ] maxP \max_{0 \le j \le b} pref[j]maxPmax0≤j≤b​pref[j]。若m a x P 0 maxP 0maxP0则该堆栈最大利润为0 00不买且无需记录购买数量。否则将m a x P maxPmaxP加入总最大利润t o t a l P r o f i t totalProfittotalProfit并记录所有满足p r e f [ j ] m a x P pref[j] maxPpref[j]maxP的j jj值存入列表c a n d i d a t e s candidatescandidates。步骤3 \texttt{3}3. 若所有堆栈的m a x P maxPmaxP均为0 00且没有候选购买数量即所有m a x P ≤ 0 maxP \le 0maxP≤0则总购买数可能为0 00。否则用集合p o s s i b l e possiblepossible记录所有可能的购买总数初始为{ 0 } \{0\}{0}。对于每个堆栈的候选列表与当前集合做笛卡尔积求和生成新集合。最后筛选出大于等于某一最小值的值实际上所有组合都是可行的因为每个堆栈独立达到其最大利润。但若t o t a l P r o f i t 0 totalProfit 0totalProfit0则购买总数只能为0 00因为所有堆栈利润为0 00但若某个堆栈有利润为0 00的多个购买数量则购买总数可能不为0 00但总利润仍为0 00所以这些也是可行方案。所以无需额外筛选直接输出集合中的所有值升序若超过10 1010个则输出前10 1010个。步骤4 \texttt{4}4. 输出最大利润和可能的购买总数列表。注意若某个堆栈m a x P 0 maxP 0maxP0则其候选列表为{ 0 } \{0\}{0}因为不购买利润为0 00但m a x P maxPmaxP应为0 00而非负数。因此处理时若m a x P 0 maxP 0maxP0将m a x P maxPmaxP设为0 00且该堆栈的候选列表为{ 0 } \{0\}{0}。代码实现// Trade on Verweggistan// UVa ID: 812// Verdict: Accepted// Submission Date: 2016-12-12// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intprofit[60][30],w,b[30],cases0;vectorvectorintpruls;while(cinw,w0){memset(profit,0,sizeof(profit));pruls.clear();intmaxProfit0;for(inti0;iw;i){cinb[i];if(b[i]0){for(intj1;jb[i];j){cinprofit[i][j];profit[i][j]10-profit[i][j]profit[i][j-1];}profit[i][0]profit[i][1];for(intj1;jb[i];j)profit[i][0]max(profit[i][0],profit[i][j]);if(profit[i][0]0){vectorintnumber;if(profit[i][0]0)number.push_back(0);maxProfitprofit[i][0];for(intj1;jb[i];j)if(profit[i][j]profit[i][0])number.push_back(j);pruls.push_back(number);}}}if(cases0)cout\n;coutWorkyards cases\n;coutMaximum profit is maxProfit.\n;coutNumber of pruls to buy:;if(pruls.size()0)cout 0\n;else{intminimum0;for(autogroup:pruls)minimumgroup.front();if(maxProfit0)minimum0;setintboxes{0};for(autogroup:pruls){setintnext(boxes);boxes.clear();for(autobox:next)for(autosingle:group)boxes.insert(boxsingle);}intoutputed0;for(autobox:boxes)if(boxminimumoutputed10)cout box;cout\n;}}return0;}总结本题通过为每个堆栈计算前缀利润并记录达到最大利润的所有购买数量然后使用集合动态生成所有可能的购买总数组合。关键点在于若某个堆栈最大利润为负应视为利润0 00且购买数量为0 00。输出时按升序输出若超过10 1010个则只输出前10 1010个最小的。该解法时间复杂度O ( w × b × 候选数量 ) O(w \times b \times \text{候选数量})O(w×b×候选数量)由于b ≤ 20 b \le 20b≤20候选数量有限运行高效。动态规划组合生成是本题的难点需正确维护所有可能总和。