P17205 Tnemerced Tnemercni 题解

· · 题解

先考虑 B 对于固定数组的代价。

根据贪心，我们可以知道，假设区间已经等于某个 b，我们只需要将区间反复减 1，就可以用 k\times b 的代价拿下。如果目前数组不是常数，就可以先用 \sum_i |a_i-b_i| 的单点修改，把它修成一个符合的样子，再压平。

所以我们可以枚举最后的样式，得到：

注意到 B 不可能更省了，因为最后钦定了 b 之后，在 $b_i$ 上单点操作至少要操作 $|a_i-b_i|$ 这么多，区间操作每次只能开启段，所以至少也需要 $\sum_i \max(b_i-b_{i-1},0)$。 考虑如何干掉 $b$ 的枚举。我们考虑拆掉绝对值和 max。 考虑 $|x| = \max_{t\in[-1,1]} tx, \max(x,0) = \max_{u\in[0,1]}ux$。因为 $t,u$ 对于每个 $i$ 都是独立的，所以原式可以写成： $C(a) =\min_b \max_{t,u} \{\sum_i t_i(a_i-b_i)+k\sum_i u_i(b_i-b_{i-1})\}$，其中 $t_i\in[-1,1],u_i\in[0,1]$。 之后使用对偶定理（即 $\min_b\max_{t,u}()$ 等价于 $\max_{t,u}\min_b()$，考虑对于每个 $b_i$，其系数就是 $k(u_i-u_{i+1})-t_i$，如果某个系数不是 $0$，那么就一定不最优，这是因为 $\min$ 会把 $b_i$ 干成正负无穷，所以最优的时候必有 $t_i=k(u_i-u_{i+1})$。 代入之后就可以得到 $C(a) = \max_t \sum_{i}t_ia_i$，其中 $t_i = k(u_i-u_{i+1}),t_i\in[-1,1],u_i\in[0,1],u_{n+1}=0$。 令 $s_i=ku_i$，则 $t_i=s_i-s_{i+1}$，约束就是：$0\leq s_i\leq k,s_i-s_{i+1}\in[-1,1]$。然后就变成 $C(a)=\max_s \sum_i (s_i-s_{i+1})a_i$。 那么回到博弈，若 A 一定会想要最大化 $\sum_i t_i a_i$。所以若 $t_i>0$，则 $a_i=r_i$，若 $t_i<0$，则 $a_i=l_i$，不然就随便选不影响。写进一个就可以表示为 $\max(t_i l_i,t_i r_i)$，再拆一下就是 $t_ir_i+\max(0,-t)(r_i-l_i)$，令 $d_i=r_i-l_i$，则 $i$ 的贡献就是：$(s_i-s_{i+1})r_i+\max(s_{i+1}-s_i,0)d_i$。 求和的时候，第一项可以变为 $\sum_i (s_i-s_{i+1})r_i=\sum_i s_i(r_i-r_{i-1})$。 令 $c_i=r_i-r_{i-1}$，则答案就是 $\max_s \{\sum_is_ic_i+\sum_i \max(s_{i+1}-s_i,0)d_i\}$。 枚举 $s$ 不现实，但 $s$ 相邻两项的约束较强，所以考虑 DP。 定义 $f(i,ns)$ 表示我考虑 $i$ 到 $n$，且 $s_i=ns$ 的时候，所能得到的最大贡献。 转移的话，从 $i+1$ 转移，$s_{i+1}$ 只能取 $ns+1,ns,ns-1$ 三个值，所以要写转移式就是： $$f_{i,ns}=ns c_i+\max_{p\in\{ns+1,ns,ns-1\}}\{f_{i+1,p}+\max(p-ns,0)d_i\}$$。 边界的话注意 $f_{n,1}=c_n$。 答案就是 $\max_sf_{1,s}$。