题目描述约翰计划进行一次钓鱼旅行。他有hhh小时1≤h≤161 \le h \le 161≤h≤16可用区域内有nnn个湖泊2≤n≤252 \le n \le 252≤n≤25沿一条单向道路依次排列。约翰从湖泊111出发可以在任意湖泊结束。他只能从湖泊iii前往湖泊i1i1i1且不必在每个湖泊停留。从湖泊iii到湖泊i1i1i1所需的旅行时间以555分钟为单位记为tit_iti​0ti≤1920 t_i \le 1920ti​≤192。每个湖泊iii的初始555分钟内预期钓到fif_ifi​条鱼之后每555分钟预期钓获量减少did_idi​条若减少后的值小于等于000则后续预期为000。所有钓鱼时间必须是555分钟的倍数。要求规划行程使预期钓获的总鱼数最大并输出每个湖泊花费的分钟数。若有多个最优方案选择在湖泊111停留时间最长的若仍并列选择在湖泊222停留时间最长的依此类推。输入格式输入包含多个测试用例。每个测试用例的第一行为整数nnn。第二行为整数hhh。第三行为nnn个整数fif_ifi​1≤i≤n1 \le i \le n1≤i≤n。第四行为nnn个整数did_idi​1≤i≤n1 \le i \le n1≤i≤n。第五行为n−1n-1n−1个整数tit_iti​1≤i≤n−11 \le i \le n-11≤i≤n−1。输入以n0n 0n0结束。输出格式对于每个测试用例输出一行包含每个湖泊停留的分钟数用逗号和空格分隔。下一行输出Number of fish expected: x其中xxx为最大预期鱼数。不同测试用例的输出之间用一个空行分隔。样例输入2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0样例输出45, 5 Number of fish expected: 31 240, 0, 0, 0 Number of fish expected: 480 115, 10, 50, 35 Number of fish expected: 724题目分析由于道路是单向的约翰只能从湖泊111依次向后移动且不能返回。因此若他决定在湖泊111到kkk之间钓鱼则旅行时间为∑i1k−1ti×5\sum_{i1}^{k-1} t_i \times 5∑i1k−1​ti​×5分钟剩余时间全部用于在这些湖泊中分配钓鱼。在每个湖泊内钓鱼的收益随投入时间递减但不同湖泊之间相互独立。对于固定的一组湖泊最优策略是每次将555分钟分配给当前预期钓获量最大的湖泊因为每次选择都是独立的且总时间有限贪心选择局部最优可达到全局最优。然而为了满足输出方案中的字典序最大化即靠前的湖泊尽量多分配时间需要在动态规划中维护最优路径。解题思路采用记忆化搜索动态规划。定义状态dp[i][m]\textit{dp}[i][m]dp[i][m]表示当前位于湖泊iii从000开始索引已经花费了mmm分钟包括旅行和钓鱼从湖泊iii到n−1n-1n−1能获得的最大预期鱼数。状态转移分为两类操作操作1\texttt{1}1. 不在湖泊iii停留直接前往湖泊i1i1i1花费ti×5t_i \times 5ti​×5分钟若in−1i n-1in−1收益为dp[i1][mti×5]\textit{dp}[i1][m t_i \times 5]dp[i1][mti​×5]。若in−1i n-1in−1则无法继续移动收益为000。操作2\texttt{2}2. 在湖泊iii停留若干个555分钟停留时间xxx从555到h−mh-mh−m以555为步长递增。停留期间按顺序计算每个555分钟内的预期钓获量第一段为fif_ifi​第二段为max⁡(fi−di,0)\max(f_i - d_i, 0)max(fi​−di​,0)第三段为max⁡(fi−2di,0)\max(f_i - 2d_i, 0)max(fi​−2di​,0)依此类推。总鱼数为这些段之和再加上dp[i1][mxti×5]\textit{dp}[i1][m x t_i \times 5]dp[i1][mxti​×5]若in−1i n-1in−1否则加上000。在转移时使用数组used[i][m]\textit{used}[i][m]used[i][m]记录达到最优值时在湖泊iii停留的分钟数。当某个选择的收益大于当前最优收益时更新used[i][m]\textit{used}[i][m]used[i][m]若收益相等则优先选择停留时间更长的方案即较大的xxx因为后续回溯时会先处理较大的xxx从而满足“靠前湖泊尽量多停留”的要求。具体实现中先计算“不停留”的收益然后对停留时间xxx从小到大枚举由于使用比较后枚举的相等收益会覆盖先前的因此最终会保留最大的xxx。递归边界当ini nin或mhm hmh时收益为000。最终从状态dp[0][0]\textit{dp}[0][0]dp[0][0]出发通过used\textit{used}used数组回溯得到每个湖泊的停留分钟数并累加旅行时间得到总花费。时间复杂度为O(n×H×(H/5))O(n \times H \times (H/5))O(n×H×(H/5))其中Hh×60H h \times 60Hh×60为总分钟数但h≤16h \le 16h≤16H≤960H \le 960H≤960状态数约25×9602400025 \times 960 2400025×96024000每次转移枚举停留时间最多约H/5≤192H/5 \le 192H/5≤192次总计算量约为24000×192≈4.6×10624000 \times 192 \approx 4.6 \times 10^624000×192≈4.6×106完全可行。空间复杂度为O(n×H)O(n \times H)O(n×H)。代码实现// Gone Fishing// UVa ID: 757// Verdict: Accepted// Submission Date: 2018-09-23// UVa Run Time: 0.190s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn,h,fi[32],di[32],ti[32];intcache[32][1024],used[32][1024];intdfs(intidx,intminutes){if(idxn||minutesh)return0;if(~cache[idx][minutes])returncache[idx][minutes];intfishes0,most0,nextfi[idx],temp;// No Stop, continue to next lake.tempdfs(idx1,minutesti[idx]*5);if(tempmost){mosttemp;used[idx][minutes]0;}// Stay and fishing.for(intmminutes5;mh;m5){fishesnext;tempfishesdfs(idx1,mti[idx]*5);if(tempmost){mosttemp;used[idx][minutes]m-minutes;}// Use first then subtract.if(nextdi[idx])next0;elsenext-di[idx];}returncache[idx][minutes]most;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinn,n0){cinh;h*60;for(inti0;in;i)cinfi[i];for(inti0;in;i)cindi[i];for(inti0;in-1;i)cinti[i];memset(cache,-1,sizeof(cache));memset(used,0,sizeof(used));dfs(0,0);if(cases0)cout\n;for(inti0,m0;in;i){if(i)cout, ;if(mh){coutused[i][m];mused[i][m]ti[i]*5;}elsecout0;}cout\n;coutNumber of fish expected: cache[0][0]\n;}return0;}总结本题通过动态规划枚举每个湖泊的停留时间并利用记忆化搜索和路径记录在最大化总鱼数的同时满足字典序优先的约束。关键在于状态转移中考虑“不停留”和“停留”两种情况并通过比较规则保留更优的停留时长。由于hhh较小状态空间有限算法效率足够。该解法亦可看作带路径记录的多阶段决策问题适用于具有顺序依赖和收益递减特性的资源分配场景。