解题思路
编号 1..m 互不相同,方案必须写成递增序列,因此本题就是在组合上加两个过滤条件。
- 从左到右按编号递增做回溯:当前已经选了若干个,下一个只能选更大的编号。这样枚举顺序就是字典序,不必再排序。
- 相邻冲突可以直接写进搜索起点:若刚选了 i,下一个起点设为 i+g+1,则相邻编号差一定大于 g。t=1 时没有相邻对,只检查单个负荷是否落在区间内。
- 取满 t 个后再看负荷和是否落在闭区间 [lo,hi]。符合条件的方案全部计数,但只把前 3 份存下来输出。
- m≤20,组合数最大约 C(20,10)=184756,直接搜即可。常见假解:把 ≤g 写成 <g(差恰好等于 g 时会多算)、只输出方案不统计总数、或 g=0 时仍禁止相邻编号。