绝对值的性质

记 $\vert a\vert \Leftrightarrow abs(a)$

$\vert a \vert =\begin{cases}
a, a \geq 0 \\
-a, a \leq 0 \\
\end{cases}$

$\vert a-b \vert = \max(a,b)-\min(a,b)$

$\vert a-b \vert = \max\{a-b,b-a\}$

$\max(a,b)=\frac{a+b+\vert a-b \vert}{2}$

$\min(a,b)=\frac{a+b-\vert a-b \vert}{2}$

例题

leetcode 1330. 翻转子数组得到最大的数组值

题意

给定一个数组 $a$ ,可以翻转(reverse)一个区间一次

求 $\sum \vert a_i-a_{i+1} \vert$ 最大值

思路1

观察发现

  1. 翻转一个数(长度为 1 的区间)不变

  2. 翻转后改变的值只和所选区间左右端点有关,区间中间的贡献无影响

我们先计算出没有翻转(或者翻转一个数)情况下的值记为 $base$

设翻转区间为 $[l, r]$

则翻转后值为 $base-\vert a_{l}-a_{l-1}\vert-\vert a_{r}-a_{r+1}\vert+\vert a_{l-1}-a_{r}\vert+\vert a_{l}-a_{r+1}\vert$

记 $dif=-\vert a_{l}-a_{l-1}\vert-\vert a_{r}-a_{r+1}\vert+\vert a_{l-1}-a_{r}\vert+\vert a_{l}-a_{r+1}\vert$

$\because \vert a-b \vert = \max(a-b,b-a)$

$\therefore$ 拆开绝对值后 $a_{l-1},a_{r}$ 异号, $a_{l},a_{r+1}$ 异号

记 $f_1, f_2 \in \{1,-1\}$

$dif=f_1a_{l-1}+f_2a_{l}-\vert a_{l}-a_{l-1}\vert-(f_1a_{r}+f_2a_{r+1}+\vert a_{r}-a_{r+1}\vert)$

记 $F(l)=f_1a_{l-1}+f_2a_{l}-\vert a_{l}-a_{l-1}\vert$

$G(r)=f_1a_{r}+f_2a_{r+1}+\vert a_{r}-a_{r+1}\vert$

要使得 $dif$ 最大,即求 $\max F(l)-\min G(r)$

枚举所有情况

思路2

记 $dif=-\vert a_{l}-a_{l-1}\vert-\vert a_{r}-a_{r+1}\vert+\vert a_{l-1}-a_{r}\vert+\vert a_{l}-a_{r+1}\vert$

因为 $l, r$ 之间关系难料,不妨考虑拆掉 $l, r$ 有关的项

不妨假设 $a_{r} \leq a_{l-1}$ , 如果条件不成立,就重新假设我们翻转的是 $[r, l]$ 就成立了(逃

咳咳,总之他们的关系没有影响,但一定要严谨得来说的话,设变量 $i, j$

  • 如果 $a_{r} \leq a_{l-1}, i=l,j=r$
  • 如果 $a_{l-1} \leq a_{r}, i=r+1,j=l-1$

如此这般,保证了 $a_{r} \leq a_{i-1}$

$
\begin{aligned}
dif&=-\vert a_{l}-a_{l-1}\vert-\vert a_{r}-a_{r+1}\vert+\vert a_{l-1}-a_{r}\vert+\vert a_{l}-a_{r+1}\vert \\
dif&=-\vert a_{i}-a_{i-1}\vert-\vert a_{j}-a_{j+1}\vert+\vert a_{i-1}-a_{j}\vert+\vert a_{i}-a_{j+1}\vert \\
&=a_{i-1}-\vert a_{i}-a_{i-1}\vert+\vert a_{i}-a_{j+1}\vert-a_{j}-\vert a_{j}-a_{j+1}\vert \\
\end{aligned}
$

此时分类讨论(上面的不算)

  • 如果 $a_{j+1} \leq a_{i}$

    $
    \begin{aligned}
    dif&=a_{i-1}+a_{i}-\vert a_{i}-a_{i-1}\vert-(a_{j}+a_{j+1}+\vert a_{j}-a_{j+1}\vert) \\
    &=2\times\big( \min(a_{i-1},a_{i})-max(a_{j}, a_{j+1}) \big )
    \end{aligned}
    $

    此时要求最大值,则最大化 $\min(a_{i-1},a_{i})$ 最小化 $max(a_{j}, a_{j+1})$

    就是分别取最值嘛

  • 如果 $a_{i} \leq a_{j+1}$

    $dif=a_{i-1}-a_{i}-\vert a_{i}-a_{i-1}\vert-(a_{j}-a_{j+1}+\vert a_{j}-a_{j+1}\vert)$

    $\because a_{i-1}-a_{i}-\vert a_{i}-a_{i-1}\vert \leq 0, a_{j}-a_{j+1}+\vert a_{j}-a_{j+1}\vert \geq 0$

    $\therefore dif \leq 0$

最后记得特判一下 $l = 0$ 或者 $r=n-1$ 的情况

hdoj6435 Problem J. CSGO

题意

有 $n$ 个 $MW$ 类物品和 $m$ 个 $SW$ 类物品

每个物品有一个属性 $S$ 和 $K$ 个属性 $X$

求 $S_{MW}+S_{SW}+\sum\limits_{i=1}^{k} \vert X_{MW}[i]-X_{SW}[i] \vert$ 的最大值

$n \leq 10^5, K \leq 5$

思路

想必聪明的你一定注意到了 $K$ 的取值范围,此中一定有鬼!

$\vert a-b \vert = a-b$ 或 $b-a$

我们不妨考虑物品每个属性的符号,我们选定的两个物品的同种属性的符号一定是相反的

那么无非两种情况,一正一负,一负一正,我们猜测要么正确,要么相反

正确不用管,我们看一下如果猜错了 设正确答案是 $a-b \geq 0$ ,猜测为 $b-a \leq 0$

猜错得到的结果肯定劣于正确结果,那我们就可以放心大胆的枚举所有情况了

详细地说就是记录物品每种属性取正负($2^k$ 种)情况下的贡献

合并两种物品只要保证这两种物品的属性选取正负完全相反即可(位运算)

贪心可得当物品属性选取正负确定时,要取值最大的物品

感觉讲起来没有代码清楚

$O(nk2^k)$

$O(n2^k)$

codeforces1093G. Multidimensional Queries

题意

与上一题(hdoj)类似,区别是多次询问,求给定区间内的最大值

思路

加以数据结构维护最值即可(口胡起来真容易

这里用了单点修改区间查询的线段树

赏