← 返回题目列表

AtCoder · asprocon8_a

A. 自动化涂装线

中文机器翻译题面 查看原题

题目说明

一条自动涂装线由 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),目标是最大化得分。