《染色》的新做法

· · 个人记录

场切了，但是我的做法好像和所有人都不一样，因此记录之。

考虑对答案 可能 有贡献的，一定是两个距离最近的、相等的数字。我们定义 \text{lst}_i 表示 i 左边最靠近 i 且满足 a_i=a_j 的 j。那么问题就转化为计算一个区间 [\text{lst}_i,i] 能否产生贡献（即 a_{\text{lst}_i} 和 a_i 能否产生贡献）。

那么我们考虑 dp。定义 dp_i 表示选择前 i 个形如 [\text{lst}_i,i] 的区间，能产生的贡献的最大值。

那么我们观察区间 [\text{lst}_i,i] 和 [\text{lst}_j,j] 能同时选，应该满足什么条件。(以下默认 j < i。)

  1. 若 j \le \text{lst}_i，则这两个区间没有互相影响，则这两个区间可以随意染色，端点染一种颜色，中间染第二种颜色。
  2. 若 \text{lst}_j > \text{lst}_i 且 \text{lst}_j = j-1，则可以直接将 (\text{lst}_i,i) 区间染成同种颜色。在这种情况下，j 依然可以产生贡献。
  3. 若 j > \text{lst}_i + 1，则这两个区间的端点必须异色，并且 (\text{lst}_i,i) 的范围内不能有异色的。但是这真的能做到吗？显然不可能，因为 j 区间的左端点也在这个区间中。
  4. 若 j = \text{lst}_i + 1，则这个染色是可以完成的。因为可以将 i,j 染相反颜色，然后可以满足要求。

接下来我们来考虑实现细节。

  1. 可以用 upper_bound 找到第一个 \le \text{lst}_i + 1 的 j，进行转移。单次转移复杂度 O(\log n)。
  2. 可以用前缀和维护在一个区间中有多少个 \text{lst}_i = i-1 进行转移。单次转移复杂度 O(1)。

那么这题就做完了，复杂度 O(n \log n)。代码如下：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
using namespace std;
int T,n,a[N],col[N],ans,t[N*5],lst[N];
int l[N],r[N],tot,dp[N],sum[N];
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
    return ret*f;
}
inline void write(int k)
{
    if(k<0)putchar('-'),k=-k;
    int nnum[20],ttp=0;
    while(k)nnum[++ttp]=k%10,k/=10;
    if(!ttp)nnum[++ttp]=0;
    while(ttp)putchar(nnum[ttp--]^48);
}
signed main()
{
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    T=read();
    while(T--)
    {
        n=read(),tot=0;
        for(int i=1;i<=n;i++)sum[i]=dp[i]=0;
        for(int i=1;i<=n;i++)a[i]=read(),t[a[i]]=0;
        for(int i=1;i<=n;i++)lst[i]=t[a[i]],t[a[i]]=i;
        for(int i=1;i<=n;i++)if(lst[i])
        {
            l[++tot]=lst[i],r[tot]=i;
            if(r[tot]==l[tot]+1)sum[tot]=a[i];
        }
        for(int i=1;i<=tot;i++)sum[i]+=sum[i-1];
        for(int i=1;i<=tot;i++)
        {
            int pos=upper_bound(r,r+i,l[i]+1)-r-1;
            dp[i]=max(dp[i-1],dp[pos]+sum[i-1]-sum[pos]+a[r[i]]);
        }
        write(dp[tot]),putchar('\n');
    }
    return 0;
}