解题思路
编号 1..m 互不相同,方案必须写成递增序列,因此本题就是在组合上加两个过滤条件。
- 从左到右按编号递增做回溯:当前已经选了若干个,下一个只能选更大的编号。这样枚举顺序就是字典序,不必再排序。
- 相邻冲突可以直接写进搜索起点:若刚选了 i,下一个起点设为 i+g+1,则相邻编号差一定大于 g。t=1 时没有相邻对,只检查单个负荷是否落在区间内。
- 取满 t 个后再看负荷和是否落在闭区间 [lo,hi]。符合条件的方案全部计数,但只把前 3 份存下来输出。
- m≤20,组合数最大约 C(20,10)=184756,直接搜即可。常见假解:把 ≤g 写成 <g(差恰好等于 g 时会多算)、只输出方案不统计总数、或 g=0 时仍禁止相邻编号。
题目内容
出题官要编一套算法题。现有 m 个知识点模块可供调用,模块各自带着互不重复的编号(取值 1 到 m)以及一项难度系数。
调用这些模块拼成一道题时,须遵守下列约定:
- 模块选择:在共计 m 个模块里取出 t 个,用来构成该题
- 顺序排列:已取出的 t 个模块须依编号从小到大排好
- 冲突检测:紧挨着的两个模块禁止出现「知识冲突」。两模块编号相减后取绝对值,只要不大于 g,就判定为冲突
- 难度约束:已取出的 t 个模块,其难度系数加总后必须落在闭区间 [lo,hi] 里
请枚举全部符合上述约定的组题方案。
输入描述
- 首行给出五个整数 m,t,g,lo,hi
- m:模块一共有多少个(1≤m≤20)
- t:取出几个模块(1≤t≤m)
- g:判定冲突用的阈值(0≤g≤m)
- lo:难度加总的下限(1≤lo≤1000)
- hi:难度加总的上限(lo≤hi≤1000)
- 次行给出 m 个整数,即各模块的难度系数(1≤ 难度系数 ≤100)
输出描述
- 首行打印符合约定的方案个数
- 个数一旦为正,再按字典序打印至多前 3 份方案(一份占一行,模块编号之间以空格隔开)
样例1
输入
6 3 1 8 16
4 2 5 3 6 1
输出
3
1 3 5
1 3 6
1 4 6
说明
- 编号依次为 1 到 6,对应难度系数 4,2,5,3,6,1
- 取出 3 个模块,紧邻编号差必须大于 1,难度加总落在 [8,16]
- 间隔够格的三元组里:
- (1,3,5):合法,加总 4+5+6=15
- (1,3,6):合法,加总 4+5+1=10
- (1,4,6):合法,加总 4+3+1=8
- (2,4,6):间隔够,但加总 2+3+1=6,低于下限
- 因而合法方案共 3 份,按字典序即上面三行