问题描述

我们需要同时完成两道料理的步骤序列，每个步骤有：

完成所需时间 $A_i$ 或 $B_j$

时间限制 $S_i$ 或 $T_j$（必须在该时间前完成才能得分）

得分 $P_i$ 或 $Q_j$（可能为负）

目标是最大化总得分。

---

关键观察

1.步骤顺序固定：每道料理的步骤必须按顺序完成

2.时间累加性：完成IOI盖饭前$i$步的总时间为 $\sum_{k=1}^i A_k$，完成JOI咖喱前$j$步的总时间为 $\sum_{k=1}^j B_k$

3.交错执行：可以在两道料理的步骤间切换，但每个步骤一旦开始就不能中断

数学模型

定义变量

设完成IOI盖饭前$i$步和JOI咖喱前$j$步的时刻为： $t_A(i) = \sum_{k=1}^i A_k$, $t_B(i) = \sum_{k=1}^i B_k$

状态表示

考虑用动态规划，设 $dp[i][j]$ 表示完成IOI前$i$步和JOI前$j$步的最大得分。

状态转移：

如果最后一步是IOI的第$i$步：

$$dp[i][j]=dp[i-1][j]+\begin{cases} P_i   ift_A(i)+t_B(i) \le S_i \\ 0   otherwise \end{cases} $$

如果最后一步是JOI的第$j$步：

$$dp[i][j]=dp[i][j-1]+\begin{cases} Q_j   ift_A(i)+t_B(i) \le T_j \\ 0   otherwise \end{cases} $$

因此：

$$dp[i][j]=max(dp[i−1][j]+scoreA(i,j), dp[i][j−1]+scoreB(i,j)) $$

其中：

$$scoreA[i][j]=\begin{cases} P_i   ift_A(i)+t_B(i) \le S_i \\ 0   otherwise \end{cases} $$$$scoreB[i][j]=\begin{cases} Q_j   ift_A(i)+t_B(i) \le T_j \\ 0   otherwise \end{cases} $$

优化挑战

直接DP的复杂度是$O(NM)$，对于$N,M \le 10^6$不可行。

---

优化思路

关键性质

注意到整个过程是沿着从$(0,0)$到$(N,M)$的网格路径，我们实际上是在选择一条路径最大化得分。

将问题重新表述：在二维网格上，从$(0,0)$走到$(N,M)$，只能向右或向上移动：

向右移动$(i-1,j) \to (i,j)$：可能获得$P_i$（如果$t_A(i) + t_B(j) \le S_i$）

向上移动$(i,j-1) \to (i,j)$：可能获得$Q_j$（如果$t_A(i) + t_B(j) \le T_j$）

条件转化

对于IOI的第$i$步，能在位置$(i,j)$获得$P_i$的条件是：

$$t_A(i)+t_B(j) \le S_i⟺t_B(j) \le S_i-t_A(i)$$

即存在一个$j$的临界值$J_i$，当$j \le J_i$时可以获得$P_i$。

类似地，对于JOI的第$j$步，能在位置$(i,j)$获得$Q_j$的条件是：

$$t_A(i)+t_B(j) \le T_j⟺t_A(i) \le S_i-t_B(j)$$

即存在一个$i$的临界值$I_j$，当$i \le I_j$时可以获得$Q_j$。

新模型

定义：

$J_i = \max{j \mid t_B(j) \le S_i - t_A(i)}$（如果$S_i - t_A(i) < 0$则$J_i = -1$）

$I_j = \max{i \mid t_A(i) \le T_j - t_B(j)}$（如果$T_j - t_B(j) < 0$则$I_j = -1$）

现在问题转化为：在网格路径上，当路径经过$(i,j)$且$j \le J_i$时获得$P_i$，当路径经过$(i,j)$且$i \le I_j$时获得$Q_j$。

进一步优化

考虑使用带优化的动态规划或数据结构优化。

设$f[j]$表示走到$(i,j)$（对于某个固定的$i$）的最大得分。

状态转移：

$$f[j]=max(f[j],f[j-1]+在(i,j)出可能获得的Q_j)$$

当$i$增加时，对于所有$j \le J_i$，我们可以给$f[j]$加上$P_i$。

这提示我们可以使用线段树或平衡树来维护$f$数组，支持：

区间加（当$i$增加时给$j \le J_i$的$f[j]$加$P_i$）

前缀最大值查询和单点更新（处理向上移动的转移）

---

算法框架

预处理前缀和$t_A(i)$和$t_B(j)$

预处理临界值$J_i$和$I_j$

使用数据结构维护DP数组，按$i$从小到大处理

最终答案为$f[M]$

---

时间复杂度

预处理：$O(N+M)$

主算法：$O((N+M)\log M)$（使用合适的数据结构）

这样可以在$N,M \le 10^6$的范围内解决问题。

---

总结

本题的关键是将原问题转化为网格路径问题，通过分析条件发现可以预处理临界值，然后使用数据结构优化动态规划。这种"二维网格路径+条件得分+数据结构优化"的思路在JOI等竞赛中很常见。

核心公式总结：

时间约束：$t_A(i) + t_B(j) \le S_i$ 或 $t_A(i) + t_B(j) \le T_j$

临界值：$J_i = \max{j \mid t_B(j) \le S_i - t_A(i)}$

状态转移：$f[j] = \max(f[j], f[j-1] + Q_j \cdot [i \le I_j])$