UVa 10261 Ferry Loading双车道轮渡装载问题迭代解法求思路提示

题目规则 #

给定按固定顺序排队、长度已知的汽车队列，以及一艘配有两条固定长度装载车道的轮渡。装载时不得跳过队列中的任意汽车，若当前无法装载下一辆汽车则直接终止操作，求轮渡最多可装载的汽车数量。

核心解题思路 #

这道题可以用滚动数组优化的动态规划迭代实现，核心是利用双车道总占用长度的关联特性压缩状态：

• 状态设计：用布尔数组dp[j]表示处理完前k辆车时，其中一条车道的占用长度为j的状态是否可达。因为前k辆车的总长度可以通过前缀和快速得到，另一条车道的占用长度就是前缀和 - j，不需要额外存储。
• 初始化：dp[0] = true，0辆车时双车道均为空，状态合法。同时预处理前缀和数组pre_sum，pre_sum[k]表示前k辆汽车的总长度。
• 迭代更新：按顺序遍历每一辆汽车，参考01背包的滚动数组更新逻辑，从大到小遍历可能的车道占用长度，避免重复计算：
  • 若当前状态dp[j]为true，尝试将当前车放到第一条车道：如果j + 当前车长 ≤ 单车道最大长度，则标记dp[j + 当前车长] = true
  • 同时尝试将当前车放到第二条车道：计算当前第二条车道的占用长度为pre_sum[k-1] - j，如果该值加当前车长不超过单车道最大长度，则当前dp[j]状态可以保留
• 终止判断：每处理完一辆车，检查dp数组中是否还有值为true的状态。如果没有，说明当前车无法装载，最大装载量就是上一轮处理的车辆数；如果所有车都处理完成，最大装载量就是总车数。

优化提示 #

• 空间复杂度可优化到O(L)，L为单条车道的最大长度，不需要开二维DP数组。
• 每次遍历车道长度时，只需要遍历到当前前缀和与L的较小值即可，减少无效计算。
• 若所有车辆的总长度小于等于单条车道长度，可直接返回总车数，无需走DP流程。

内容的提问来源于stack exchange，提问作者WilliamHarvey