题目描述在一个N×MN \times MN×M的网格中每个格子都放有一个机器人。这些机器人可以执行四种命令NORTH所有机器人向上北移动一格SOUTH所有机器人向下南移动一格WEST所有机器人向左西移动一格EAST所有机器人向右东移动一格。执行一条命令时如果某个机器人移出了网格它会被立即摧毁且之后无法再执行任何命令。给定每种命令的总数你可以任意安排这些命令的执行顺序目标是使得所有机器人实际执行命令的总次数最大化。输入格式输入包含多组测试数据。每组数据第一行包含两个正整数NNN和MMM1≤N,M≤1051 \le N, M \le 10^51≤N,M≤105分别表示网格的行数和列数。第二行包含四个整数依次为NORTH、SOUTH、WEST、EAST四种命令的数量每个数均不超过10510^5105。输入以一行0 0结束。输出格式对于每组数据输出一行Case X: Y其中XXX是测试用例编号从111开始YYY是最大总执行次数。答案保证在646464位有符号整数范围内。样例输入2 2 1 0 0 0 2 2 1 1 1 1 0 0输出Case 1: 4 Case 2: 9题目分析所有机器人同时执行同一条命令。在某条命令执行之前如果历史上向北移动的总位移最大值为max⁡R\max RmaxR最小值为min⁡R\min RminR则行方向的历史跨度最大最小位移之差为Rspanmax⁡R−min⁡RR_{\textit{span}} \max R - \min RRspan​maxR−minR。同理定义列方向的历史跨度CspanC_{\textit{span}}Cspan​。此时所有存活机器人的行坐标必须位于[1,N−Rspan][1, N - R_{\textit{span}}][1,N−Rspan​]范围内列坐标必须位于[1,M−Cspan][1, M - C_{\textit{span}}][1,M−Cspan​]范围内因此当前存活的机器人数量为cur(N−Rspan)×(M−Cspan) \textit{cur} (N - R_{\textit{span}}) \times (M - C_{\textit{span}})cur(N−Rspan​)×(M−Cspan​)执行每一条命令前所有存活机器人都会执行它因此该命令的贡献就是当前的cur\textit{cur}cur。一旦某个方向的跨度达到其网格尺寸例如Rspan≥NR_{\textit{span}} \ge NRspan​≥N则cur\textit{cur}cur变为000之后所有命令的贡献均为000。问题转化为给定四种移动指令的数量如何安排顺序使得每一步的cur\text{cur}cur累加和最大。观察发现相反方向的成对指令如NORTH和SOUTH如果交替执行其历史跨度只会从000变为111之后不会继续增加。这种“配对”的指令收益高且不压缩后续空间应优先执行。当某一方向的两种相反指令数量不等时剩余的单向指令会迫使跨度逐步增加。此时应选择当前剩余空间更大的方向执行即比较N−RspanN - R_{\textit{span}}N−Rspan​与M−CspanM - C_{\textit{span}}M−Cspan​优先执行空间较大者。解题思路1. 统一方向简化判断对于每一组数据我们先将南北、东西两对方向的数量整理为“大数”和“小数”使得cntNorth≥cntSouth,cntWest≥cntEast \textit{cntNorth} \ge \textit{cntSouth}, \quad \textit{cntWest} \ge \textit{cntEast}cntNorth≥cntSouth,cntWest≥cntEast这样配对数量即为较小的那个数剩余单向指令为两者的差。2. 决定先处理哪个方向的配对先处理东西配对还是南北配对会影响后续的剩余空间因此需要分别估算两种顺序的总收益并选择较大的那个。定义如果先执行东西配对共cntEast\textit{cntEast}cntEast对每一对两条指令执行后列跨度变为111收益为N×(M−1)N \times (M-1)N×(M−1)除第一对的第一条收益为N×MN \times MN×M外随后处理剩余的WEST指令再处理南北配对及剩余NORTH指令。同理先执行南北配对也有对应的收益估算。我们通过两个表达式gainFirstEW和gainFirstNS分别计算两种顺序的预估值若先南北更优则交换NNN与MMM同时交换南北与东西的计数使得后续代码统一按“先东西后南北”处理。3. 执行东西配对与多余西向指令若存在cntEast0\textit{cntEast} 0cntEast0执行 $ \text{cntEast}$ 对东西交替指令收益为N(M−1)⋅N⋅cntEast⋅2 N (M-1) \cdot N \cdot \textit{cntEast} \cdot 2N(M−1)⋅N⋅cntEast⋅2其中第一对的第一条收益为NNN之后每对两条指令的收益均为N×(M−1)N \times (M-1)N×(M−1)。然后处理剩余的WEST指令即cntWest - cntEast。若还有剩余执行一条WEST收益为N×MN \times MN×M列跨度变为111同时有效列数MMM减111。将剩余的WEST指令数限制为不超过当前有效列数因为超过部分执行时收益为000。4. 循环处理剩余的WEST和NORTH可能还有SOUTH此时EAST已清空SOUTH可能仍然存在如果cntNorth cntSouth。在每一步若SOUTH 0则有两种选择开始执行南北配对消耗掉所有SOUTH以及与之一一配对的NORTH这会使行跨度变为111有效行数NNN减111并可能留下剩余NORTH继续执行一条WEST列跨度继续增加。计算两种选择的预估收益选择收益更大的方案。若没有WEST指令则只能执行南北配对。当SOUTH清空后只剩下WEST和NORTH两种单向指令。此时每一步选择当前剩余空间更大的方向执行即比较当前有效行数和列数若行数大则执行NORTH否则执行WEST。如果只剩一种方向如只有NORTH则连续执行该方向的指令收益形成一个等差数列可直接用公式求和收益列数×剩余指令数×2×行数−剩余指令数12 \text{收益} \text{列数} \times \text{剩余指令数} \times \frac{2 \times \text{行数} - \text{剩余指令数} 1}{2}收益列数×剩余指令数×22×行数−剩余指令数1​同理处理只剩WEST的情况。5. 正确性说明贪心选择的正确性基于以下事实配对指令不增加历史跨度应尽早执行因为越早执行收益越大此时剩余空间最多。当必须增加某一方向的跨度时选择剩余空间更大的方向执行可以使得当前的(N−Rspan)×(M−Cspan)(N - R_{\text{span}}) \times (M - C_{\text{span}})(N−Rspan​)×(M−Cspan​)尽可能大从而保证每一步都取得局部最优且该贪心策略可通过交换论证证明其全局最优。6. 复杂度分析每组数据只需要常数次算术运算和循环循环次数等于实际可执行的指令数但指令总数不超过4×1054 \times 10^54×105因此时间复杂度为O(总指令数)O(\text{总指令数})O(总指令数)。空间复杂度O(1)O(1)O(1)。代码实现// Robot// UVa ID: 1622// Verdict: Accepted// Submission Date: 2026-06-25// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongLL;intmain(){LL nRows,nCols;// 行数、列数intcaseNo1;while(cinnRowsnCols,nRows||nCols){LL cntNorth,cntSouth,cntWest,cntEast;cincntNorthcntSouthcntWestcntEast;LL answer0;// 保证 cntNorth cntSouth, cntWest cntEastif(cntNorthcntSouth)swap(cntSouth,cntNorth);if(cntWestcntEast)swap(cntEast,cntWest);// 计算两种优先顺序的预估收益决定先东西还是先南北LL gainFirstEWnRows(nCols-1)*nRows*cntEast*2(nCols-1)(nCols-1)*(nRows-1)*cntSouth*2;LL gainFirstNSnColsnCols*(nRows-1)*cntSouth*2(nRows-1)(nCols-1)*(nRows-1)*cntEast*2;if(cntWest-cntEast){gainFirstEW(nCols-1)*nRows;gainFirstNS(nCols-1)*(nRows-1);}if(cntNorth-cntSouth){gainFirstEW(nCols-1)*(nRows-1);gainFirstNSnCols*(nRows-1);}// 若先南北更优则交换行列及对应的方向计数if(gainFirstEWgainFirstNS){swap(nRows,nCols);swap(cntNorth,cntWest);swap(cntSouth,cntEast);}boolhasExecutedEWPairtrue;// 是否已执行过东西配对// 执行东西配对cntEast 对if(cntEast){answernRows(nCols-1)*nRows*cntEast*2;cntWest-cntEast;cntEast0;--nCols;hasExecutedEWPairfalse;}// 处理多余的向西指令if(cntWest){answernCols*nRows;--cntWest;if(hasExecutedEWPair)--nCols;}// 超过列数的向西指令无法执行截断cntWestmin(nCols,cntWest);// 处理剩余的西向和北向指令可能还有南向while(cntWest||cntNorth){if(cntSouth){// 比较“先南北配对”与“继续向西”的收益LL t1nCols*nRows(nRows-1)*nCols*2*cntSouth;LL t2nCols*nRows(nCols-1)*nRows(nCols-1)*(nRows-1)*(2*cntSouth-1);if(cntNorth-cntSouth){t1nCols*nRows(nRows-1)*nCols*(2*cntSouth1);t2nCols*nRows(nCols-1)*nRows(nCols-1)*(nRows-1)*2*cntSouth;}if(t1t2||!cntWest){// 执行南北配对answernColsnCols*(nRows-1)*cntSouth*2;cntNorth-cntSouth;cntSouth0;--nRows;if(cntNorth){answernCols*nRows;--cntNorth;}cntNorthmin(nRows,cntNorth);}else{// 继续向西answernCols*nRows;--nCols;--cntWest;}}elseif(!cntWest){// 仅剩北向等差数列answernCols*cntNorth*(2*nRows-cntNorth1)/2;cntNorth0;}elseif(!cntNorth){// 仅剩西向等差数列answernRows*cntWest*(2*nCols-cntWest1)/2;cntWest0;}else{// 两者都有选择剩余空间较大的方向answernCols*nRows;if(nColsnRows){--nCols;--cntWest;}else{--nRows;--cntNorth;}}}coutCase caseNo: answerendl;}return0;}总结本题的核心是将复杂的指令排序问题转化为历史跨度变化与收益函数的贪心决策。关键技巧包括将相反方向的指令视为“配对”配对指令不增加跨度应优先执行通过预估两种配对的执行顺序来做出全局最优选择在单向指令阶段采用“选择剩余空间较大方向”的贪心策略并用等差数列求和优化连续执行。该解法充分利用了问题的几何特性避免了状态搜索时间复杂度仅为线性适合大数据范围。