题解：P11233 [CSP-S 2024] 染色（民间数据）

· · 题解

Solution

容易想到 O(n^2) 的 dp，设状态 f_{i,j} 为前 i 个数字中，第 [j,i] 的颜色相同，第 j-1 的颜色不同的最大得分。
转移为

f_{i,j}=\left\{ \begin{aligned} \max^{i-1}_{k=1}{f_{i-1,k}+[a_{k-1}=a_{i}]\times a_i},i=j\\ f_{i-1,j}+[a_{i-1}=a_i] \times a_i,i>j \end{aligned} \right.

这个式子是不能直接优化的，我们需要贪心一下，其实第一个方程只需要找到最大的 k 使得 a_k=a_j就行了，令其为 last，再把第一维滚掉，式子便优化成了

f_j=\left\{ \begin{aligned} \max(\max^{i-1}_{k=1}{f_k},f_{last+1}+a_i),i=j\\ f_j+[a_{i-1}=a_i]\times a_i,i>j \end{aligned} \right.

每个 i 对应的 last 可以直接维护，第一条式子用一个变量直接维护最大值，再加上单点查，第二条式子需要区间加，可以用树状数组实现。

PS：可以不用树状数组，直接用一个标记维护全局加的操作，更新 f_i 的时候提前减去当前标记，这样用到 f_i 的时候加上现在的全局加标记就是 f_i 的真实取值。

Code

O(n \log n)（赛时代码）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5,M=1e6;
int t,n,a[N+5],tre[N+5],mp[N+5];
vector<int>g[M+5];
int lb(int x){return x&-x;}
void add(int x,int y){for(int i=x;i<=n;i+=lb(i))tre[i]+=y;}
int query(int x){int ret=0;for(int i=x;i>=1;i-=lb(i))ret+=tre[i];return ret;}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],g[a[i]].push_back(i),mp[i]=g[a[i]].size()-1;
        int ans=0;
        for(int i=1;i<=n;i++){
            if(mp[i]){
                int val=max(ans,query(g[a[i]][mp[i]-1]+1)+a[i]);
                add(i,val),add(i+1,-val);
            }
            else add(i,ans),add(i+1,-ans);
            int val=(a[i]==a[i-1])*a[i];
            add(1,val),add(i,-val);
            ans=max(ans+val,query(i));
        }
        cout<<ans<<'\n';
        for(int i=1;i<=n;i++)tre[i]=0;
        for(int i=1;i<=n;i++)g[a[i]].clear();
    }
}

Thanks

在此感谢 zzzz1234567 大佬帮我将原本 O(n \log n) 的复杂度优化为 O(n)，感谢 sgxsz 大佬帮我用线段树实现来证明了我原本的复杂度的正确性，感谢 Cindy_Li 大佬指出文中的批漏。