拿 Welcome to Tokyo! 举例。
列出规划式
\[\begin{aligned}
\max_{a_i,b_i \ge 0} & \sum_{i=1}^n a_i \\
\sum a_i \le & \sum_{j \in [l_i,r_i]} b_j \\
a_i \le & 1 \\
\sum b_j = & k \\
\end{aligned}
\]
为减轻记忆负担，化为 \(\min - \sum a\)，将所有 constraint 化为 \(=0\) 或 \(\le 0\)。
\[\begin{aligned}
\min_{a_i,b_i \ge 0} & -\sum a_i \\
\sum a_i - \sum_{j \in [l_i,r_i]} b_j \le & 0 \\
a_i - 1 \le & 0 \\
(\sum b) - k = & 0 \\
\end{aligned}
\]
为每个约束设乘子，约束为非负数（\(\max\) 则为非正数），加到 objective 中。特别地若该约束为等式则乘子不做限制。
\[\begin{aligned}
\max_{x_i,y_i \ge 0} \min_{a_i,b_i \ge 0} & -\sum a_i \\
& + x_i(\sum a_i - \sum_{j \in [l_i,r_i]} b_j) \\
& + y_i(a_i - 1) \\
& + t((\sum b) - k)\\
\end{aligned}
\]
整理 primal 变量的系数。
\[\begin{aligned}
\max_{x_i,y_i \ge 0} \min_{a_i,b_i \ge 0} & -(\sum y) - tk \\
& + \sum a_i (x_i + y_i - 1) \\
& + \sum b_j (t - \sum_{j \in [l_i,r_i]} x_i) \\
\end{aligned}
\]
这里可以理解为两个玩家在进行游戏，外层玩家掌控 \(x_i,y_i\)，由于 \(a_i,b_i \ge 0\)，因此他应该让其系数非负，否则内层选手可以取到 \(-\infty\)。
去除 primal 变量，得到对偶形式。
\[\begin{aligned}
\max_{x_i,y_i \ge 0} & -(\sum y) - tk \\
x_i + y_i - 1 \ge & 0 \\
t - \sum_{j \in [l_i,r_i]} x_i \ge & 0 \\
\end{aligned}
\]
整理得
\[\begin{aligned}
\min_{x_i,y_i \ge 0} & (\sum y) + tk \\
x_i + y_i \ge & 1 \\
\sum_{j \in [l_i,r_i]} x_i \le & t \\
\end{aligned}
\]
视 \(t\) 为常数，其组合意义为对每个区间做决策是否对序列加 1，要求序列中每个位置不超过 \(t\) 最小化不加 1 的区间个数。
对每个 \(t\) 求出答案后双指针即可求得所有 \(k\) 的答案。