题解：P17728 [SCP-J 2026] 染色 / color

· · 题解

一道诈骗题，典型的贪心。

解题思路

首先看题目，题目要求出数列 A 每个位置元素与往左第一个同色元素的差之和能取得的最大值。关键的突破口就是我们可以把所有位置划分成两个集合：染成红色的和染成蓝色的。由于两种颜色互换并不会造成什么影响，所以我们设 X 为染成一种颜色的位置集合，Y 为染成另一种颜色的位置集合。我们对于这两个部分分别计算对应位置 C_i 的值总和，最后加起来。

依题意得，C_{X_1}=0，C_{X_i}=A_{X_i}-A_{X_{i-1}}。如果有 k 个位置在 X 集合中，那么我们需要求 \displaystyle \sum_{i=2}^k C_{X_i}=\sum_{i=2}^k A_{X_i}-A_{X_{i-1}}。展开这个式子：

\begin{aligned} \sum_{i=2}^k A_{X_i}-A_{X_{i-1}} &= (A_{X_2}-A_{X_1})+(A_{X_3}-A_{X_2})+\cdots +(A_{X_k}-A_{X_{k-1}}) \\ &=-A_{X_1}+A_{X_2}-A_{X_2}+A_{X_3}-A_{X_3}+\cdots+A_{X_{k-1}}-A_{X_{k-1}}+A_{X_k}\\ &=A_{X_k}-A_{X_1} \end{aligned}

消得只剩两项！我们有希望了。这就是著名的裂项相消 / 望远镜求和，也可以理解为对差分数组求前缀和可以得到原数组的元素。

如法炮制，我们把 \displaystyle \sum_{i=2}^{n-k} C_{Y_i} 也化简成了 A_{Y_{n-k}}-A_{Y_1}。两个式子的和就是 A_{X_k}-A_{X_1}+A_{Y_{n-k}}-A_{Y_1}，我们的目标是最大化这个值。看起来有四项，似乎很难维护。

接下来是第二个关键观察：因为 A_1 和 A_n 和其他元素一样需要染色，所以它们必定在 X 集合和 Y 集合内。又因为不可能出现在 A_1 左边或在 A_n 右边的数，因此 1 一定是它所在颜色位置集合的第一个（下标 1），n 一定是它所在颜色位置集合的最后一个（下标 k 或 n-k）。

分类讨论：

不管怎样，原式都变为了 A_{n}-A_{1} 加上两个数的差的形式。这样就好办了：我们只要找到 A 中符合要求的两个数的差的最大值。当固定被减数的位置 i，减数的位置就可以在 [0,i+1] 中选择。要使差最大，减数就得尽量小。于是我们计算前缀最小值，对每个位置的数维护选择这个位置可以得到的最大的差，每次选择当前前缀范围中最小的数作为减数。最后还要进行特判，因为可能存在全部染成一种颜色的情况，这种情况下答案为 A_{n}-A_{1}。

时间复杂度分析

处理读入和前缀最小值数组 O(n)，遍历数组找最大差 O(n)，总 O(n)，能过 2\times 10^5。

AC code

考场上饭堂了，循环起点写错，喜提 88 分。以下是本蒟蒻赛后通过的代码。

:::success[代码]

#include<bits/stdc++.h>
#define ios cin.tie(0)->sync_with_stdio(0)
#define int i64
#define inf 0x7f7f7f7f7f7f7f7f
using namespace std;
typedef long long i64;
int a[202020],b[202020];

signed main()
{
    int n,ans=-inf;
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",a+i);
        if(i) b[i]=min<int>(b[i-1],a[i]);
        else b[i]=inf;
    }
    if(n==2){//小数据可以直接特判，避免出错
        printf("%lld",max(a[1]-a[0],0ll));
        return 0;
    }
    if(n==3){
        printf("%lld",max<int>({a[2]-a[1],a[1]-a[0],a[2]-a[0]}));
        return 0;
    }
    b[n]=b[n-1];
    for(int i=0;i<n-1;i++){
        ans=max<int>(ans,a[i]-b[i+1]);
    }
    ans=max<int>(ans,0ll);
    printf("%lld",ans+a[n-1]-a[0]);
    return 0;
}

:::