NOIP 提高组初赛 · NOIP 2010 提高组初赛试题 第 28 题

（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在伸手不见五指的黑夜里，过桥时必须借照灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多能承受两个人同时经过，否则将会坍塌。每个人单独过独木桥都需要一定的时间，不同的人要的时间可能不同。两个人一起过独木桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间。现在输入 $N(2\leq N<1000)$ 和这 $N$ 个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸。

例如，有 $3$ 个人甲、乙、丙，他们单独过桥的时间分别为 $1,2,4$，则总共最少需要的时间为 $7$。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为 $2+1+4=7$。

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false;
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;

int n,hour[SIZE];
bool pos[SIZE];

int max(int a,int b)
{
    if(a>b)
       return a;
    else
       return b;
}
int go(bool stage)
{
    int i,j,num,tmp,ans;
    if(stage==RIGHT_TO_LEFT)
    {
        num=0;
        ans=0;
        for(i=1;i<=n;i++)
           if(pos[i]==RIGHT)
           {
      

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题是经典的过河 DP。拿到题先别急着填，心里得有个动态规划的大框架：状态是'右岸剩哪些人'，转移分两步，一步是两人过桥（取慢的），一步是单人送灯返回。只要抓住'两人过桥后灯必须回来'这个核心，再结合代码里递归的调用顺序，空就自然出来了。

最容易栽跟头的是把送灯那一步想反了，以为送灯是'两人一起送'，其实送灯只能是一个人，而且送完还得把状态改回来（回溯）。另外，很多人会忽略递归调用时参数的方向，把 go(LEFT_TO_RIGHT) 写成 go(RIGHT_TO_LEFT)，结果逻辑全乱套。还有就是那个判断右岸人数的条件，写成 num <= 1 就错了，因为两个人也能一起过，只有剩 1 个或 0 个时才能直接过。

这道题考查的是简单动态规划（或称递归搜索、状态压缩 DP）。命题人特别喜欢用这种'过河'模型来考察学生对状态转移和递归回溯的掌握，因为代码里直接体现了 DP 的'分而治之'思想：把大问题拆成'两人过桥'和'单人送灯'两个小问题，然后递归求解。

我们先用人话把概念捋顺：

• 状态：用布尔数组 pos 记录每个人在左岸还是右岸（true 为左，false 为右）。
• 转移：从当前状态出发，要么让右岸的两个人一起过到左岸（耗时取较慢者），要么让左岸的一个持灯人送回右岸（耗时就是他的单独时间）。
• 递归：函数 go(stage) 负责处理特定方向的移动。stage 是 RIGHT_TO_LEFT（送灯）或 LEFT_TO_RIGHT（过桥）。
• 回溯：每次递归调用前必须保存现场（比如把 pos 改回去），否则状态会错乱，这是 DP 递归实现的关键技巧。

命题视角上，出题人挖坑很细：

• 送灯时，如果右岸只剩≤2人，直接一起过即可，不需要再递归送灯，否则会死循环或算错。
• 过桥时，必须从'左岸'选人送回，参数方向不能搞反。
• 送灯的人选必须是左岸现有的，且要把 pos 改回去。

现在咱们逐空推演，就像在考场上一步步想：

空①（RIGHT_TO_LEFT 分支，送灯前判断） 代码里先统计右岸人数 num。如果 num <= 2，说明右岸只剩 1 或 2 个人，他们可以直接一起过桥到左岸，灯也自然带过去了，任务结束，直接返回 ans（即这两人的最大时间）。如果写成 num <= 1 就漏掉了两人一起过的情况，算出来的时间会偏大；写成 num < 2 也一样错。所以①填 num <= 2（或 num < 3）。

空②（送灯后递归） 当右岸有≥3人时，必须选两人过桥。两人过桥后，灯在左岸，必须有人送回去。代码里先计算两人过桥的耗时 tmp = max(hour[i], hour[j]) + ???。这里的'???'就是送灯的时间，而送灯的动作正是另一个递归调用 go(LEFT_TO_RIGHT)（从左岸送回右岸）。所以②填 go(LEFT_TO_RIGHT)。

空③（LEFT_TO_RIGHT 分支，选人） 过桥时，我们要从左岸选两个人。循环条件里写的是 if(??? )，显然是在筛选左岸的人。pos[i] 为 true 表示在左岸，所以条件就是 pos[i] == LEFT（或 LEFT == pos[i]）。

空④（过桥耗时计算） 选中的这个人要单独送灯回去，耗时是 hour[i]，送灯后还要继续处理剩下的问题，即递归调用 go(RIGHT_TO_LEFT)。所以总耗时是 hour[i] + go(RIGHT_TO_LEFT)（顺序可换）。

空⑤（回溯） 递归调用后必须恢复现场，把 pos[i] 改回右岸，否则下一次循环会误以为这个人还在左岸。所以⑤填 pos[i] = LEFT。

算法主线与计算演示 以题目给的例子 N=3，时间 1,2,4 为例：

• 初始右岸 3 人，num=3>2，进入送灯分支。
• 枚举两人过桥：

- 选 1 和 2：过桥耗时 2，送灯耗时 go(LEFT_TO_RIGHT)。在 LEFT_TO_RIGHT 里，左岸有 1 和 2，选 1 送灯耗时 1+go(RIGHT_TO_LEFT)。此时右岸剩 4，num=1<=2，直接过桥耗时 4。总耗时 2+1+4=7。 - 选 1 和 4：过桥 4，送灯 1+go(RIGHT_TO_LEFT)（右岸剩 2,4，选 2 送灯耗时 2+go(RIGHT_TO_LEFT)→右岸剩 4，过桥 4），总 4+1+2+4=11。 - 选 2 和 4：过桥 4，送灯 2+go(RIGHT_TO_LEFT)（右岸剩 1,4，选 1 送灯耗时 1+go(RIGHT_TO_LEFT)→右岸剩 4，过桥 4），总 4+2+1+4=11。

• 最小值是 7，与答案一致。

易错点再强调

• ①写成 num <= 1 会漏掉两人一起过，导致答案偏大。
• ②写成 go(RIGHT_TO_LEFT) 会形成死循环（灯送过去又送回来）。
• ③写成 pos[i] == RIGHT 就选错人了。
• ④漏掉递归调用或顺序写反，逻辑不通。
• ⑤忘记回溯，状态污染，后面循环会重复选人。

考频与趋势 从题库数据看，'简单动态规划'这一考点在 NOIP 及 GESP 中非常活跃：题库共考过 94 题，覆盖 8 个考试级别（2009-2026）。逐年分布显示，2023 年考了 15 题，2024 年 23 题，2025 年更是高达 25 题，2026 年也有 13 题，说明近四年该考点热度持续上升。分赛事来看，GESP 六级考了 34 题、七级 27 题，NOIP 提高组初赛 10 题，GESP 八级 10 题，CSP 入门级 5 题、提高级 4 题，GESP 五级 3 题，NOIP 普及组初赛 1 题。整体呈现'中高级别高频、低级别也有稳定出现'的态势。

预测 基于上述数据，动态规划类题目在未来两年（2027-2028）仍将是初赛和 GESP 六级/七级的常客，出题形式大概率延续'过河'、'装箱'、'路径规划'等经典模型，但可能会结合更复杂的约束（如桥承重变化、多人同时过桥的分组策略等）来增加区分度。暂无足够依据预测具体年份的题量，但可以肯定的是，掌握递归回溯和状态压缩的 DP 思路，是应对这类题目的核心能力。