Steven_Meng's Blog

传送门

建议先做这道题，有一些套路是一模一样的。

考虑如何$dp$，$dp[i][j]$表示现在扫到第$i$个数，用了$j$段区间，最大的总价值，$cnt(l,r)$表示在区间$[l,r]$中不同的数的个数。

考虑在区间$[1,p]$分段，很容易列出$dp$方程：

$dp[i][j]=\max \{ dp[p][j-1]+cnt(p+1,i) \}$

其中$$1 \le p \le i-1$$

容易算出，枚举$i$复杂度为$O(k)$，枚举$p$复杂度为$O(n)$，计算$cnt$复杂度为$O(n)$

总复杂度为$O(n^2k)$，会$TLE$

考虑如何优化，发现复杂度瓶颈在寻找最大值和计算$cnt$，考虑线段树优化。

考虑计算数组$lst[i]$，表示颜色$a[i]$上一次出现的地方，这个$O(n)$ 在输入时预处理即可。

对于$dp$数组每一层，每次跑$dp$都重建一个线段树。

发现枚举到$a[i]$，$[lst[i],i-1]$都要$+1$，因为只有对于区间$[p,i] (p \in [lst[i],i-1])$，$a[i]$才算新出现的元素。

查询时，查询$[0,j-1]$$dp$数组最大值即可。

时间复杂度$O(kn\log n)$

代码里面$dp$数组下标从$0$开始是为了更方便地计算$[0,j-1]$$dp$数组最大值

#include <bits/stdc++.h>
#define MAXN 35005
#define MAXM 51
using namespace std;
int dp[MAXM][MAXN];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar(); 
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace SegmentTree{
    struct node{
        int l,r;
        int maxn,tag;
    }tree[MAXN<<2];
    #define lc i<<1
    #define rc i<<1|1
    inline void pushup(int i){
        tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
    }
    inline void pushdown(int i){
        if (tree[i].tag){
            tree[lc].tag+=tree[i].tag;
            tree[lc].maxn+=tree[i].tag;
            tree[rc].tag+=tree[i].tag;
            tree[rc].maxn+=tree[i].tag;
            tree[i].tag=0;
        }
    }
    void Build(int i,int lev,int l,int r){
        tree[i].l=l,tree[i].r=r;
        tree[i].tag=0;
        if (l==r){
            tree[i].maxn=dp[lev][l];
            return ;
        }
        int mid=(l+r)>>1;
        Build(lc,lev,l,mid);
        Build(rc,lev,mid+1,r);
        pushup(i);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            tree[i].maxn+=val;
            tree[i].tag+=val;
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    int Query(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i].maxn;
        }
        int mid=(tree[i].l+tree[i].r)>>1,ans=0;
        pushdown(i);
        if (L<=mid) ans=max(ans,Query(lc,L,R));
        if (mid<R) ans=max(ans,Query(rc,L,R));
        return ans;
    }
}
using namespace SegmentTree;
int lst[MAXN],lstcolor[MAXN];
int a[MAXN];
//lst[i]表示a[i]这种颜色最后出现的位置
//lstcolor[i]表示颜色i最后出现的位置
//类似于一个链表吧。。。
int main(){
    int n=read(),k=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
        lst[i]=lstcolor[a[i]];
        lstcolor[a[i]]=i;
    }
    for (register int i=1;i<=k;++i){
        Build(1,i-1,0,n);
        for (register int j=1;j<=n;++j){
            Update(1,lst[j],j-1,1);
            dp[i][j]=Query(1,0,j-1);
        }
    }
    printf("%d\n",dp[k][n]);
}