题解

思路推导

选择顺序只与最后一次选择的排数和列编号有关。若最后选择了第一排第 $i$ 名学生，那么此前最后选择的学生必须在第二排且列编号小于 $i$；第二排同理。

设 $f_{r,i}$ 表示以第 $r$ 排第 $i$ 名学生结尾时能够得到的最大身高总和。直接枚举此前另一排的结尾位置可以得到二次转移。进一步观察到，处理列 $i$ 时只需要知道另一排在前 $i-1$ 列中的最大状态值，因此可以维护两个前缀最大值，将转移降为常数时间。

做法

从左到右扫描每一列。用 $best_0,best_1$ 分别表示已经处理过的列中，以第一排、第二排学生结尾的最大总和。当前列选择第一排时，只能接在第二排状态后，候选值为 $h_{1,i}+best_1$；选择第二排同理。先用旧状态计算两个候选值，再更新两个前缀最大值。

最终答案为两个前缀最大值中的较大者。由于所有身高均为正数，空队伍不会优于非空队伍。

正确性证明

对列编号归纳。处理第 $i$ 列前，假设 $best_r$ 等于所有以第 $r$ 排且列编号不超过 $i-1$ 的学生结尾的合法队伍最大总和。

任何以第一排第 $i$ 名学生结尾的合法队伍，其倒数第二名学生若存在，必在第二排且列编号小于 $i$。根据归纳假设，这部分队伍的最大总和为 $best_1$，所以加入当前学生后最优值为 $best_1+h_{1,i}$。反之，取到 $best_1$ 的合法队伍后接当前学生一定仍合法，因此该值可以达到。第二排的论证完全相同。

更新前缀最大值后，归纳假设对下一列仍成立。扫描结束时，每个合法非空队伍都以某一排的某一列结尾，故两个前缀最大值的较大者就是全局最优答案。

复杂度分析

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。