题解：P17728 [SCP-J 2026] 染色 / color
ymhh
·
·
题解
P17728 [SCP-J 2026] 染色 / color
我感觉我好废物啊，连橙题都没写出来。
一、题意
自行理解。
二、思路
1、一些观察
观察同颜色分数计算式子：
C_{sum}=\sum\limits_{i=L+1}^{R} a_i-a_{i-1}
你会发现，这个式子展开后就会消掉大部分内容，也就是：
C_{sum}=\sum\limits_{i=L+1}^{R} a_i-a_{i-1}=a_R-a_L
2、运用
因此总分数 = a_{R_1} - a_{L_1} + a_{R_2} - a_{L_2}，其中 L_1, R_1 分别为红色区间的起点和终点，L_2, R_2 分别为蓝色区间的起点和终点。
考虑如何让这个式子最大。
你会发现红色与蓝色的位置是对称的（意思就是：不用管这个点到底是蓝色还是红色，答案是一样的），因此不妨分类讨论：1 和 n 是同色，或 1 和 n 是异色。
不妨设 1 是红色。
首尾同色
红色贡献是 a_n-a_1。
蓝色可以从 2 \sim n-1 选择左右端点，因此最大贡献是：
\max\left(0,\max\limits_{2\le i<j\le n-1}(a_j-a_i)\right)
:::info[提示]{open}
之所以与 0 取 \max，是因为可能没有蓝色。
:::
首尾异色
此时贡献是：
(a_{R_1}-a_1)+(a_n-a_{L_2})=(a_n-a_1)+(a_{R_1}-a_{L_2})
不难发现变量为 a_r-a_b（其中 r 为红色终点 R_1，b 为蓝色起点 L_2）。
限制条件为：
\begin{cases}
1 \le r \le n-1 \\
2 \le b \le n \\
r \ge b-1
\end{cases}
其中 r \ge b-1 是为了防止出现格子没有染色的情况。
三、算法实现
这个很简单，枚举一个参数消掉它，再用变量维护即可。
四、代码
:::info[AC 代码]
不想给
:::
五、总结&trick
1、望远镜求和
我也不知道为什么叫这个名字
\sum\limits_{i=L+1}^{R} a_i-a_{i-1}=a_R-a_L
这个貌似挺经典的，而且小学的裂项也学过；但是赛时没有把式子写出来，导致没看出来，还是要 多动笔 啊！
2、对称性
这个本质就是消参吧：因为它对称，所以可以假令。
这个要 多尝试 吧。
3、闲话
这是我第一次在橙题里学到这么多东西，感谢洛谷。