AT_hokudai_hitachi2022_b 農機シェアリング計画動的最適化問題
题目描述
[problemUrl]: https://atcoder.jp/contests/hokudai-hitachi2022/tasks/hokudai_hitachi2022_b
在本题中，你需要在农机共享服务中，最大限度地利用所拥有的机械和人员（下文统称为“工人”），以获得最多的报酬来承接农作业（下文称为“作业”）。你需要从空间中分布的大量作业中自行决定要承接哪些作业，并在提交/修正作业执行计划的同时，指挥工人实际处理这些作业。每个作业由多个小作业“任务”组成，工人需按规定数量处理这些任务才能视为完成，基本上承接的作业都必须完成（未完成将产生罚分）。完成作业可以获得报酬，但根据处理任务的时间点不同，报酬量也不同，因此需要考虑合适的作业时间段进行处理。此外，每个时间点可执行的任务数取决于工人的处理能力和天气，天气会在一定时间间隔内给出预报。
*报酬：假定为农作物的适宜收获期、纳米电网向农机供给的可再生能源利用率等。
  
最初将给出以下输入信息：
1. 作业期间
2. 地理信息（图）
3. 工人信息
4. 所有作业的信息
5. 天气相关信息
6. 计划相关信息
对此，参赛者首先需要输出：
1. 要承接的作业
之后，每个时间点开始时会输入以下信息：
1. 已承接作业的信息
2. 工人的当前位置
3. （每隔一定时间）天气预报
参赛者需要输出：
1. 作业执行计划
2. 各工人的操作
如此循环，直到作业期间结束。
评分标准为：
1. 报酬
2. 未完成作业的罚分
3. 计划变更程度与计划遵守程度
以下为详细说明。
输入格式
## 输入1
首先输入：
1. 作业期间
2. 地理信息（图）
3. 工人信息
4. 所有作业的信息
5. 天气相关信息
6. 计划相关信息
具体格式如下：
> $ T_{\rm{max}}\\
N_V\,\,N_E\\
u_1\quad\ v_1\quad\ d_1\\
\vdots\\
u_{N_E}\,\,\ v_{N_E}\,\,\ d_{N_E}\\
N_{\rm{worker}}\\
v^{\rm{init}}_1\,\,L^\text{max}_1\,\,N^{\rm{JobType}}_1\,\,\text{Type}^1_1\,\,\text{Type}^1_2\,\,\cdots\ \text{Type}^1_{N^{\rm{JobType}}_1}\\
\vdots\\
v^{\rm{init}}_{N_{\rm{worker}}}\,\,L^\text{max}_{N_{\rm{worker}}}\,\,N^{\rm{JobType}}_{N_{\rm{worker}}}\,\,\text{Type}^{N_{\rm{worker}}}_1\,\,\text{Type}^{N_{\rm{worker}}}_2\,\,\cdots\ \text{Type}^{N_{\rm{worker}}}_{N^{\rm{JobType}}_1}\\
N_{\rm{job}}\\
\text{Job}_1\\
\vdots\\
\text{Job}_{N_{\rm{job}}}\\
T^{\rm{weather}}\,\,N^{\rm{weather}}\\
\begin{array}{llll}
p^{\rm{weather}}_{1,1}\ & p^{\rm{weather}}_{1,2}\ & \cdots\ & p^{\rm{weather}}_{1,N^{\rm{weather}}}\\
p^{\rm{weather}}_{2,1}\ & p^{\rm{weather}}_{2,2}\ & \cdots\ & p^{\rm{weather}}_{2,N^{\rm{weather}}}\\
\vdots\ & \vdots\ & \ddots\ & \vdots\\
p^{\rm{weather}}_{N^{\rm{weather}},1}\ & p^{\rm{weather}}_{N^{\rm{weather}},2}\ & \cdots\ & p^{\rm{weather}}_{N^{\rm{weather}},N^{\rm{weather}}}\\
\end{array}\\
c_1\,\,c_2\,\,\cdots\,\,c_{N^{\rm{weather}}}\\
P_m\,\,\ R_m\,\,\ \alpha\\
t_1\,\,\ p^1_1\,\,\ p^1_2\,\,\ \cdots\ \,\,\ p^1_{N^{\rm{weather}}}\\
t_2\,\,\ p^2_1\,\,\ p^2_2\,\,\ \cdots\ \,\,\ p^2_{N^{\rm{weather}}}\\
\vdots\\
t_{N'}\,\,\ p^{N'}_1\,\,\ p^{N'}_2\,\,\ \cdots\ \,\,\ p^{N'}_{N^{\rm{weather}}} $
（$ \text{Job}_i $ 的结构见下文）
## 输入2（每个时刻）
输出1正常结束后，进入每个时刻的输入输出。时刻 $ t=1 $ 开始，每到输入2时，时刻加1。
每个时刻输入：
1. 当前天气
2. 已承接作业的信息
3. 工人的当前位置
4. （每 $ T^\text{weather} $ 时间输入一次）天气预报
格式如下：
> $ w\\
N^\text{selected}\\
{\rm{id}}^{\rm{job}}_1\,\,\ n^{\rm{rest}}_1\\
\vdots\\
{\rm{id}}^{\rm{job}}_{N^\text{selected}}\,\,\ n^{\rm{rest}}_{N^\text{selected}}\\
{\rm{id}}^{\rm{worker}}_1\,\,\ u_1\,\,\ v_1\,\,\ d^{\rm{from\_u}}_1\\
\vdots\\
{\rm{id}}^{\rm{worker}}_{N_{\rm{worker}}}\,\,\ u_{N_{\rm{worker}}}\,\,\ v_{N_{\rm{worker}}}\,\,\ d^{\rm{from\_u}}_{N_{\rm{worker}}} $
**每 $ T^\text{weather} $ 时间（即 $ t $ 满足 $ (t-1)\ \mod\ T^\text{weather}\ =\ 0 $ 时）**，会额外输入天气预测：
> $ t_1\,\,\ p^1_1\,\,\ p^1_2\,\,\ \cdots\ \,\,\ p^1_{N^{\rm{weather}}}\\
t_2\,\,\ p^2_1\,\,\ p^2_2\,\,\ \cdots\ \,\,\ p^2_{N^{\rm{weather}}}\\
\vdots\\
t_{N'}\,\,\ p^{N'}_1\,\,\ p^{N'}_2\,\,\ \cdots\ \,\,\ p^{N'}_{N^{\rm{weather}}} $
## 输入3（评分）
时刻 $ t=T_\text{max} $ 的 [输出2](output2) 结束后，若输出有效，则会输入分数 $ S $，格式如下：
> $ S $
输出格式
## 输出1
参赛者需选择要承接的作业，并按如下格式输出：
> $ N^{\text{selected}}\,\,\ \text{id}_1\,\,\ \text{id}_2\,\,\cdots\ \,\,\text{id}_{N^{\text{selected}}} $
（末尾需换行）
## 输出2（每个时刻）
参赛者需输出：
1. 各工人的计划
2. 各工人的操作
格式如下：
> $ N_\text{schedule}\\
\text{id}_1\,\,\text{id}_2\,\,\cdots\,\,\text{id}_{N_\text{schedule}}\\
\text{job}^{\text{id}_1}_t\,\,\text{job}^{\text{id}_1}_{t+1}\,\,\cdots\,\,\text{job}^{\text{id}_1}_{T_\text{max}}\\
\vdots\\
\text{job}^{\text{id}_{N_\text{schedule}}}_t\,\,\text{job}^{\text{id}_{N_\text{schedule}}}_{t+1}\,\,\cdots\,\,\text{job}^{\text{id}_{N_\text{schedule}}}_{T_\text{max}}\\
{\rm{action}}_1\\
{\rm{action}}_2\\
\vdots\\
{\rm{action}}_{N_{\rm{worker}}} $
（末尾需换行）
说明/提示
### 问题概要
本题要求你在农机共享服务中，合理分配工人和机械，选择并完成合适的作业，以最大化报酬。作业由多个任务组成，工人需在合适的时间、合适的天气下完成任务。每个作业有依赖关系、报酬函数、未完成罚分等。你需要根据输入的信息，选择承接哪些作业，并在每个时刻合理安排工人行动和作业计划。评分依据为总报酬、未完成作业的罚分、计划变更与遵守程度。
详细的输入输出格式、作业与工人属性、天气系统、计划系统、评分方法等请参见题面描述。
**注意：**
- 数学公式、代码、LaTeX 环境等请严格按照原文保留。
- 题目内容较长，建议分段阅读和理解。
- 题目为交互题，需根据输入动态输出结果。
- 具体的输入输出样例、评分细则、作业依赖、天气影响、计划变更等细节请参见题面。
由 ChatGPT 4.1 翻译