题意简化

$n$ 个时刻，每个时刻选择睡觉（S）或吃东西（E）：

• 睡觉：获得愉悦值 $s_i$
• 吃东西：获得愉悦值 $e_i$

约束：每个长度为 $k$ 的连续区间 $[i, i+k-1]$ 中：

• 至少有 $ms$ 个时刻睡觉
• 至少有 $me$ 个时刻吃东西

求最大总愉悦值，并输出方案。

核心思想：网络流建模

1. 转化为流量平衡问题

设 $x_i = 1$ 表示时刻 $i$ 吃东西，$x_i = 0$ 表示睡觉。

约束条件：对每个区间 $[i, i+k-1]$：

• 睡觉数 $\ge ms$ ⇒ 吃东西数 $\le k-ms$
• 吃东西数 $\ge me$ ⇒ 睡觉数 $\le k-me$

即：

$$me \le \sum_{j=i}^{i+k-1} x_j \le k-ms$$

2. 差分约束转网络流

设前缀和 $S_i = \sum_{j=1}^i x_j$，则区间和约束变为：

$$S_{i+k-1} - S_{i-1} \le k-ms$$ $$S_{i+k-1} - S_{i-1} \ge me$$

即：

$$S_{i+k-1} - S_{i-1} \in [me, k-ms]$$

同时有 $0 \le S_i - S_{i-1} \le 1$（每个时刻最多一个选择）。

3. 最小费用最大流建模

代码中的网络流模型：

• 源点 $s=0$，汇点 $t=n+1$
• 节点 $i$ 表示前缀和 $S_i$

边的含义：

1. E(0, 1, k-ms, 0)：$S_0=0$ 到 $S_1$ 的流量限制
2. E(i, i+1, k-me-ms, 0)：$S_{i+k-1} - S_{i-1} \le k-ms$ 且 $\ge me$ 的约束
3. E(max(1,i-k+1), i+1, 1, e[i]-s[i])：选择时刻 $i$ 吃东西的决策边
   • 流量1表示选择
   • 费用 $e_i - s_i$（选择吃东西比睡觉多获得的愉悦值）

4. 费用流的直观解释

初始假设所有时刻都睡觉，总愉悦值为 $\sum s_i$。

考虑将某些时刻改为吃东西：

• 获得额外愉悦值 $e_i - s_i$
• 但需满足区间约束

网络流找到一组改变，使得额外愉悦值最大且满足约束。

算法步骤

1. 建图：

   • 建立 $n+2$ 个节点
   • 添加区间约束边
   • 添加决策边：每个时刻对应一条边，流量1，费用 $e_i-s_i$

2. 跑最小费用最大流：

   • 使用带势能的Dijkstra优化
   • 初始用SPFA计算势能

3. 计算答案：

   • 基础值：$\sum s_i$
   • 加上最大费用流的值

4. 输出方案：

   • 检查每条决策边：如果流量为0（边被使用），表示选择了吃东西（E）
   • 否则选择睡觉（S）

关键点

1. 区间约束的建模技巧

将区间和约束转化为前缀和差分约束，再转化为网络流中的容量限制。

2. 决策边的巧妙设计

• 每个时刻对应一条从 $S_{i-k}$ 到 $S_i$ 的边
• 流量1表示选择
• 费用为收益差

3. 网络流规模

• 节点数：$n+2$
• 边数：$O(n)$
• 使用带势能的Dijkstra，复杂度 $O(nm\log n)$，可过 $n=1000$

代码特点

1. 网络流模板：封装了最小费用最大流
2. 势能优化：先用SPFA计算初始势能，再用Dijkstra
3. 方案输出：通过检查边的剩余流量判断选择
4. 边编号记录：id[i] 记录每个时刻对应的决策边

样例解释

输入：

5 4 2 2
4 8 6 2 2  (s_i)
4 6 9 6 0  (e_i)

约束：每个长度为4的区间要有至少2个S和2个E。

输出：SSEES

• 时刻1：S，得4
• 时刻2：S，得8
• 时刻3：E，得9
• 时刻4：E，得6
• 时刻5：S，得2 总和：4+8+9+6+2 = 29

网络流找到最优方案：将时刻3和4改为吃东西。