题解 P11233 染色

se1bo · 2024-10-28 20:29:36 · 题解

update 2024/12/15：更新了图片

讲一个在考场上独到的解析思路：

思路

不妨设：

发现：如果想让一个数有价值，就要将 a_{i} 与 a_{j} 置为一种颜色（假设为红），中间的颜色置为不同的颜色（假设为蓝）。样例：

那么我们更进一步：既然需要将中间的颜色置为同一种颜色，那我们可以将 i+1 位置与 j-1 位置连接一条边权为 a_{i} 的边。

当不相交的边的权值和最大时，即为最优情况。我们以考场大样例第一个为例子。

较为特殊的情况（如上图红色框）：若 j=i+1，那么最优的情况一定是将 a_{i} 与 a_{j} 画为同一种颜色。

证明：若 a_{i} 与 a_{j} 不为同一种颜色，那么既会得不到 a_{j} 的贡献，也不会得到某条跨过 a_{i} 与 a_{j} 的边权。相反，若 a_{i} 与 a_{j} 为同一种颜色，他们不会影响任何其他的值。

所以我们直接把 a_{i} 加入答案 ans 中。

当我们只选择边权为 13 的边时，结果最大。

求解

所以，怎么办呢？

设:

则有：

解析：要么选择这条边，那么就从 out_{i}-1 位置转移方程。因为这一段都不能选择，线不可以交叉。要么不选择，答案就是上一个点的值。

那么代码就非常容易啦：

code

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+10,N=2e5+10;
typedef long long ll;
ll n,a[N],dp[N],out[N],t[M],ans=0,v[N],p;
int main(){
    cin>>p;
    for(int k=1;k<=p;k++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(t[a[i]]){ //如果 a[i] 存在上一个数
                if(t[a[i]]==i-1){ //如果与上一个数挨着
                    ans+=a[i]; //答案直接加上
                }else{
                    out[i-1]=t[a[i]]+1;
                //将i-1 与 上一个 a[i] 的后一个连边
                    v[i-1]=a[i];//将边权设置为 a[i]
                }
            }
            t[a[i]]=i; //存下 a[i] 位置
        }
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1];
            if(out[i]) dp[i]=max(dp[i],dp[out[i]-1]+v[i]);
              // 状态转移
        }
        ans+=dp[n]; //加上特殊的答案
        cout<<ans<<'\n';
          //别忘了多组数据清空！我就因为这个T2寄了
        for(int i=1;i<=n;i++){
            t[a[i]]=0;
            a[i]=0;
            out[i]=0;
            v[i]=0;
            dp[i]=0;
        } 
        ans=0;
    }
}

时间复杂度：O(tn)

thanks！