UVa 801 Flight Planning

题目描述编写一个程序规划飞机航班每个航班由若干航段组成。需要为每个航段选择最佳飞行高度200002000020000英尺到400004000040000英尺之间以100010001000英尺为步长以最小化整个航程的燃油消耗。飞机特性固定巡航空速VCRUISE400V_{\text{CRUISE}} 400VCRUISE​400节海里/小时最经济巡航高度AOPT30000A_{\text{OPT}} 30000AOPT​30000英尺在该高度下燃油消耗率为GPHOPT2000GPH_{\text{OPT}} 2000GPHOPT​2000加仑/小时。当飞行高度偏离AOPTA_{\text{OPT}}AOPT​时每偏离100010001000英尺燃油消耗率增加GPHEXTRA10GPH_{\text{EXTRA}} 10GPHEXTRA​10加仑/小时。起飞和降落高度为000英尺每爬升100010001000英尺额外消耗CLIMBCOST50CLIMBCOST 50CLIMBCOST50加仑下降不节省也不消耗额外燃油。假设所有爬升和下降均在航段开始瞬间完成零时间因此每个航段以恒定高度和空速飞行。给定每个航段的距离海里、在200002000020000英尺和400004000040000英尺处的预期尾风节中间高度的尾风通过线性插值计算。正尾风增加地速负尾风减小地速。要求为每个航段选择高度整数千英尺使总燃油消耗最小并输出总燃油向上取整到整数加仑。输入格式第一行为一个整数NNN表示航班数量。每个航班描述如下第一行包含一个整数KKK0K1010 K 1010K101表示该航班的航段数。接下来KKK行每行三个整数航段长度海里、200002000020000英尺处的尾风节、400004000040000英尺处的尾风节。输出格式对于每个航班输出一行格式为Flight x: h1 h2 ... hK fuel其中xxx为航班编号从111开始hih_ihi​为第iii个航段选择的高度千英尺fuelfuelfuel为总燃油消耗的向上取整值。样例输入2 2 1500 -50 50 1000 0 3 1000 50 0 2000 0 20 1800 50 100样例输出Flight 1: 35 30 13986 Flight 2: 20 30 30 23502题目分析每个航段的燃油消耗由两部分组成飞行中的巡航油耗和爬升额外油耗。巡航油耗取决于飞行高度hhh千英尺和该航段的地速ggg。地速等于空速400400400节加上尾风www尾风通过线性插值计算若当前高度为20i20 i20i千英尺i∈[0,20]i \in [0,20]i∈[0,20]则尾风wiw20(w40−w20)×i/20w_i w_{20} (w_{40} - w_{20}) \times i / 20wi​w20​(w40​−w20​)×i/20。飞行时间tdistance/(400wi)t \text{distance} / (400 w_i)tdistance/(400wi​)小时。巡航耗油率r(h)200010×∣h−30∣r(h) 2000 10 \times |h - 30|r(h)200010×∣h−30∣加仑/小时。所以巡航油耗为r(h)×tr(h) \times tr(h)×t。爬升额外油耗仅当本航段高度hhh高于上一航段高度prevprevprev时才产生为50×(h−prev)50 \times (h - prev)50×(h−prev)加仑。下降不产生油耗。由于所有高度变化在航段开始时发生状态仅由上一航段结束高度决定。目标是最小化所有航段的总油耗这是一个多阶段决策问题可用动态规划求解。解题思路设航段编号为000到K−1K-1K−1高度用索引iii表示对应实际高度20i20 i20i千英尺i0,1,…,20i 0,1,\ldots,20i0,1,…,20。定义状态dp[leg][i]\textit{dp}[leg][i]dp[leg][i]表示从第leglegleg个航段开始当前飞机已处于高度iii即上一航段结束高度为iii或对于第一段初始高度为000对应i0i0i0表示地面但实际第一段必须从000英尺爬升到选择的高度时的最小剩余燃油消耗。边界条件dp[K][i]0\textit{dp}[K][i] 0dp[K][i]0无剩余航段。转移方程对于当前高度iii枚举本航段选择高度jjj0≤j≤200 \le j \le 200≤j≤20计算爬升成本cclimb50×max⁡(j−i,0)c_{\text{climb}} 50 \times \max(j - i, 0)cclimb​50×max(j−i,0)。本航段尾风wwind20[leg](wind40[leg]−wind20[leg])×j/20w wind_{20}[leg] (wind_{40}[leg] - wind_{20}[leg]) \times j / 20wwind20​[leg](wind40​[leg]−wind20​[leg])×j/20。地速g400wg 400 wg400w。飞行时间tlength[leg]/gt \text{length}[leg] / gtlength[leg]/g。巡航油耗ccruise(200010×∣j−10∣)×tc_{\text{cruise}} (2000 10 \times |j - 10|) \times tccruise​(200010×∣j−10∣)×t因为303030千英尺对应索引101010。总成本ccclimbccruisedp[leg1][j]c c_{\text{climb}} c_{\text{cruise}} \textit{dp}[leg1][j]ccclimb​ccruise​dp[leg1][j]。取所有jjj中的最小值记录最佳选择best[leg][i]jbest[leg][i] jbest[leg][i]j。由于K≤100K \le 100K≤100高度数212121时间复杂度O(K×212)O(K \times 21^2)O(K×212)空间O(K×21)O(K \times 21)O(K×21)完全可行。最终从dp[0][0]\textit{dp}[0][0]dp[0][0]初始高度为000开始但注意第一段从000英尺爬升到jjj爬升成本会正确计入因为i0i0i0表示地面。输出时从leg0leg0leg0alt0alt0alt0开始根据bestbestbest数组依次输出每段高度20best[leg][alt]20 best[leg][alt]20best[leg][alt]并更新altbest[leg][alt]alt best[leg][alt]altbest[leg][alt]。总燃油dp[0][0]\textit{dp}[0][0]dp[0][0]为浮点数需向上取整到整数加仑。使用ceil(fuel)或等价方法。代码实现// Flight Planning// UVa ID: 801// Verdict: Accepted// Submission Date: 2018-12-29// UVa Run Time: 0.090s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intK,best[128][32];doubledp[128][32],length[128],winddown[128],windup[128];doubledfs(intleg,intaltitude){if(legK)return0;if(dp[leg][altitude]0)returndp[leg][altitude];doubler1e20;for(inti0;i20;i){doublecost0;if(ialtitude)cost50.0*fabs(i-altitude);cost(fabs(i-10)*10.02000.0)*(length[leg]/(400.0winddown[leg](windup[leg]-winddown[leg])*i/20.0));costdfs(leg1,i);if(costr){rcost;best[leg][altitude]i;}}returndp[leg][altitude]r;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases;cincases;for(intcs1;cscases;cs){cinK;for(inti0;iK;i)cinlength[i]winddown[i]windup[i];for(inti0;iK;i)for(intj0;j20;j)dp[i][j]-1;coutFlight cs: ;doublefueldfs(0,0);intaltitude0;for(inti0;iK;i){cout(20best[i][altitude]) ;altitudebest[i][altitude];}// Round up but not round to nearest gallons leads to AC.coutfixedsetprecision(0)(fuel1000.5)\n;}return0;}总结本题通过动态规划在离散高度集合上搜索最优决策将航段间的爬升成本与巡航成本有机结合。状态定义为当前航段起始高度转移枚举本航段高度利用记忆化搜索避免了重复计算。时间复杂度低代码实现简洁。关键在于正确计算尾风插值和爬升成本的单向性仅爬升有成本。输出时注意高度为实际千英尺20i20 i20i燃油需向上取整。该解法适用于航段数不超过100100100的规模。