P6631 [ZJOI2020] 序列
题解
注意到原题是个整数规划，记所有操作的集合为 \(\mathcal{I}\)，操作 \(i\) 的次数为 \(x_i\) 化成标准型如下：
\[\begin{align*}
&\max\sum_{i\in\mathcal{I}}x_i\\
s.t.\ & \sum_{i\ni j}x_i=a_j & (q_j)\\
& x_i\ge 0, x_i\in \mathbb{Z}
\end{align*}
\]
注意到我们有几乎充分的理由认定该线性规划的约束矩阵 \(A\) 是一个全单模矩阵，故我们去掉 \(x_i\in\mathbb{Z}\) 的限制，做对偶，有
\[\begin{align*}
&\min\sum_{i=1}^n a_iq_i\\
s.t.\ & \forall S\in\mathcal{I},\sum_{i\in S}q_i\le 1
\end{align*}
\]
由全单模性，最有整数解存在，考虑操作 \(\{i\}\)，有 \(a_i\le 1\)，易证 \(a_i\rightarrow max(a_i,-1)\) 的替换是合法的，故 \(a_i\in\{-1,0,1\}\)，动态规划即可，复杂度 \(O(n)\)。
record
qoj5036 [集训队互测2022] 卑鄙的下毒人
题解
记前缀和为 \(b_{0...n}\) 即要求
\[\min k(b_n-b_0)+\sum\max(0,a_i-(b_{r_i}-b_{l_i-1}))\\
s.t.\ \forall i\in[0,n),b_{i+1}\ge b_i
\]
注意到原题的目标函数和约束都为差分形式，考虑最大费用循环流的对偶：
\[\min\sum cap_e\max(0, cost_e-p_u+p_v)\\
\]
建图：
- \(\text{goal}\leftarrow k(b_n-b_0)\)：\(0\xrightarrow[cost=0]{cap=k} n\)
- \(\text{goal}\leftarrow max(0,a_i-(b_{r_i}-b_{l_i-1}))\)：\(r\xrightarrow[cost=a_i]{cap=1}l-1\)
- \(\text{constrait}:b_{i+1}\ge b_i\)：\(i+1\xrightarrow[cost=0]{cap=+\infin}i\)
观察图易知答案等价于选择 \(k\) 个互不相交的集合，集合内的区间互不相交，最大化权值和。
可以直接贪心算法，又或者去掉 \(0\xrightarrow[cost=0]{cap=k} n\)，跑最大费用最大流，第一次增广由于是 DAG，按照拓扑序计算最短路，这之后使用 dijkstra algorithm。复杂度 \(O(km\log m)\)。