题解：P17205 「DLESS-6」Tnemerced Tnemercni

xiazha · 2026-08-09 15:59:57 · 题解

声明：本题解使用 AI 辅助推导。

考虑确定序列 a 之后小 B 的问题即为：

p_i - q_i + \sum_{[l,r] \ni i} (u_{l,r} - v_{l,r}) = -a_i, \quad \forall i = 1,\dots,n

最小化 ans=\sum_{i=1}^{n} (p_i + q_i) + k \cdot \sum_{{1\le l \le r\le n} } (u_{l,r} + v_{l,r})

该问题为整数线性规划问题：

我们需要将其对偶成 \max \{ b^T y : A^T y \leq c \}。

对于每个等式约束，我们引入对偶变量 s_i，则现在问题转为最大化 \sum (-a_i)s_i。

对于 p,q 我们对偶之后可得限制为 -1\le s_i\le 1。

对于 u_{l,r}，他的目标系数为 k，约束中它在所有 i \in [l,r] 的等式中约束系数为 1，则对偶约束中有 \sum_{i=l}^r s_i\le k，同理对于 v_{l,r} 推出 \sum_{i=l}^r s_i\ge -k。

考虑最大化 \sum (-a_i)s_i 与最大化 \sum a_is_i 是等价的，因为 s_i 的相反数仍在取值范围内。

现在问题转化为：

s_i \in [-1, 1], \ \forall [l, r],|\sum_{i=l}^{r} s_i |\leq k

最大化 \sum_{i=1}^{n} a_i s_i。

由于最大化那么可以忽略 \sum_{i=l}^{r} s_i <-k 的条件，因为其一定不优。

接下来回到整个问题，答案即为：

交换顺序：

在固定 s 的情况下，内层最大化是独立的：

$s_i=-1$，取 $a_i=l_i$。 $s_i=0$，无贡献。

接下来考虑 dp，那么我们只关心到 i 为止 s 的所有历史前缀和最小值 p 与目前前缀和 now，并且满足 now-p\le k 即可，我们只需在 dp 时维护 l=now-p 即可，根据 s_i 的取值 l 的变化可以 O(1) 转移。

核心代码如下：

dp[opt][j]=max(dp[opt][j],dp[opt^1][j]);
dp[opt][j+1]=max(dp[opt][j+1],dp[opt^1][j]+r[i+1]);
dp[opt][max(0ll,j-1)]=max(dp[opt][max(0ll,j-1)],dp[opt^1][j]-l[i+1]);

时空复杂度皆为 O(nk)，做完了。