题目理解

Kiana 需要在寿司餐厅中，通过选择若干连续段寿司，最大化总美味度减去总花费的差值。

• 寿司有 $n$ 种，按顺序排列，每种寿司有代号 $a_i$ 和基础美味度 $d_{i,i}$。
• 可以选择任意多个连续段，每个连续段 $[i,j]$ 提供综合美味度 $d_{i,j}$（$i \le j$）。
• 每种美味度（包括基础美味度和综合美味度）只会被计入一次。
• 花费与每种代号 $x$ 的寿司被吃的数量 $c_x$ 有关，为 $m x^2 + c_x x$，其中 $m$ 为给定常数。

问题转化为：选择若干连续段，使得这些连续段对应的美味度之和（不重复）减去因吃寿司产生的花费最大。

关键观察

1. 问题转化

选择连续段 $[i,j]$ 相当于获得美味度 $d_{i,j}$，但同时必须选择该区间内的所有寿司。
选择寿司 $i$ 会产生花费 $a_i$（线性部分），并且如果这是第一个被吃的代号为 $a_i$ 的寿司，还会产生固定花费 $m a_i^2$。

因此，问题可以转化为最大权闭合子图模型：

• 正权点：每个连续段 $[i,j]$，权值为 $d_{i,j}$（若 $i=j$，则权值为 $d_{i,i} - a_i$，因为选择单个寿司必须支付 $a_i$ 的线性花费）。
• 负权点：每个寿司 $i$（权值为 $-a_i$，表示线性花费）和每个代号 $x$（权值为 $-m x^2$，表示固定花费）。
• 依赖关系：选择连续段 $[i,j]$ 必须选择区间内的所有寿司；选择寿司 $i$ 必须选择其代号 $a_i$ 对应的点。

2. 依赖关系的优化建图

直接建图时，每个连续段 $[i,j]$ 需要向区间内每个寿司连边，边数可达 $O(n^3)$。
可以利用区间包含关系优化：对于 $[i,j]$（$i < j$），连向 $[i+1,j]$ 和 $[i,j-1]$，容量为 $+\infty$。这样，选择 $[i,j]$ 就必须选择其子区间，最终传递到每个寿司 $[k,k]$，将边数降至 $O(n^2)$。

算法设计

1. 构建网络流图

• 源点 $S$，汇点 $T$。
• 区间点：对每个 $1 \le i \le j \le n$，建立点 $id_{i,j}$。
  • 若 $i = j$，权值为 $d_{i,i} - a_i$。
  • 若 $i < j$，权值为 $d_{i,j}$。
  • 若权值 $> 0$，从 $S$ 向 $id_{i,j}$ 连边，容量为权值；否则从 $id_{i,j}$ 向 $T$ 连边，容量为 $-$权值。
  • 若 $i = j$ 且 $m = 1$，从 $id_{i,i}$ 向代号点 $a_i$ 连边，容量为 $+\infty$。
  • 若 $i < j$，从 $id_{i,j}$ 向 $id_{i+1,j}$ 和 $id_{i,j-1}$ 连边，容量为 $+\infty$。
• 代号点：对每个出现的代号 $x$，建立点 $lab_x$，从 $lab_x$ 向 $T$ 连边，容量为 $m x^2$。

2. 求解最大权闭合子图

最大权闭合子图的权值等于正权点权值和减去最小割（即最大流）。
使用 Dinic 算法求解最大流。

算法正确性

1. 建模等价性

• 选择连续段 $[i,j]$ 当且仅当对应区间点 $id_{i,j}$ 被选中（在 $S$ 侧）。
• 依赖边（容量 $+\infty$）保证：若 $id_{i,j}$ 被选中，则其子区间点（最终到寿司点）也必须被选中。
• 寿司点 $id_{i,i}$ 被选中表示吃了寿司 $i$，需支付线性花费 $a_i$，已通过权值 $d_{i,i} - a_i$ 体现。
• 若 $m=1$，通过 $id_{i,i}$ 到 $lab_{a_i}$ 的 $+\infty$ 边，保证只要吃了至少一个代号 $a_i$ 的寿司，就必须选中 $lab_{a_i}$，从而支付固定花费 $m a_i^2$。
• 最小割将图分为 $S$ 侧（选中点）和 $T$ 侧（未选中点），割边包括：
  • 未选中的正权点（放弃的美味度）。
  • 选中的负权点（支付的花费）。 因此，最小割即为放弃的美味度与支付的花费之和，正权点权和减最小割即为净收益最大值。

2. 优化建图的正确性

区间 $[i,j]$ 依赖其所有子区间，而子区间最终依赖到每个寿司 $[k,k]$（$i \le k \le j$），因此依赖关系与直接连向所有寿司等价。

复杂度分析

时间复杂度

• 点数：$O(n^2 + \max a_i)$，$n \le 100$，$\max a_i \le 1000$，约 $10^4$。
• 边数：$O(n^2)$ 条依赖边，$O(n^2)$ 条权值边，$O(n)$ 条代号边，约 $10^4$ 条。
• Dinic 算法：在一般图上复杂度为 $O(V^2 E)$，但本题图为二分图结构且容量较小，实际运行很快。

空间复杂度

• 存储图需 $O(V + E)$，在限制内。

算法标签

• 最大流
• 网络流
• 最小割
• 排列组合
• 线段树
• 最大权闭合子图

总结

本题通过转化为最大权闭合子图问题，并利用区间依赖关系优化建图，将看似复杂的区间选择与花费计算统一到网络流模型中求解，体现了图论建模的巧妙性。