题目说明
一条自动涂装线由 H 个循环移动的挂钩组成。产品有 S 种形状和 C 种颜色,形状 s、颜色 c 的产品必须生产 N_{s,c} 个。每种形状只有 K_s 个专用挂具。
连续产品的形状或颜色变化时必须留出空挂钩。形状从 s 变为 t 需要至少 A_{s,t} 个间隔,颜色从 c 变为 d 需要至少 B_{c,d} 个间隔,两项同时变化时取较大值。请完成全部产品,并尽量减少挂具更换和空挂钩。
输入
S C H a b
N_1,1 ... N_1,C
...
N_S,1 ... N_S,C
K_1 ... K_S
A_1,1 ... A_S,S
B_1,1 ... B_C,C
a 是每次安装或拆卸挂具的罚分权重,b 是每个空挂钩的罚分权重。形状切换矩阵有 S 行,颜色切换矩阵有 C 行。公开生成器中形状数和颜色数均为 4 至 10,挂钩数为 250,总产品数为 1000 至 5000。
输出
L
instruction_1
...
instruction_L
1 ≤ L ≤ 1000000。第 i 条指令作用于编号 (i-1) mod H 的挂钩:
s c:使用形状 s 的挂具生产颜色 c 的产品;-1:拆下当前挂具;-2:让当前挂钩空过。
每种产品的出现次数必须恰好等于需求;使用的某种挂具数不得超过 K_s;相邻生产指令之间必须满足形状和颜色切换间隔。
评分
设 X 为挂具安装与拆卸总次数,Y 为空挂钩数。合法输出得分为 max(1, 10000000 - a×X - b×Y),目标是最大化得分。