codeforces833B The Bakery

题面传送门

题目大意：将一个长度为n的序列分为k段，使得总价值最大，一段区间的价值表示为区间内不同数字的个数

思路：

　　显然的dp。

　　先想到一个朴素的状态转移方程 $dp[i][k]=max(dp[j][k-1]+val[j+1][i])$，$0<=j<i$ $dp[i][k]$表示到第i为，截取了k段的最大价值，val表示某一段区间的价值。

　　这样的时间复杂度是$n*n*k$，显然是不能接受的，这里面的一个n和一个k显然是不能优化的，那我们只需要把一个n优化成logn或者线性的就可以接受了，所以想到线段树优化。

　　那么我们就要维护$dp[j][k-1]+val[j+1][i]$这个的最大值，要怎么维护呢，当我们扫到一个数字x，这个数字会对哪些val造成影响呢?显然是前一个x后面的区间。加一就好了。

　　然后每次把$dp[i][k-1]$放入线段树，用滚动数组来优化空间。

　　

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
const int maxn=35010;
typedef long long ll;
int n,k,dp[2][maxn],x,le[maxn],pos[maxn],sum[maxn<<2],lazy[maxn<<2];
void pushup(int o){
    sum[o]=max(sum[o<<1],sum[o<<1|1]);
}
void pushdown(int o,int l,int r){
    int mid=(l+r)>>1;
    if(l==r)return;
    if(lazy[o]){
        sum[o<<1]+=lazy[o];
        sum[o<<1|1]+=lazy[o];
        lazy[o<<1]+=lazy[o];
        lazy[o<<1|1]+=lazy[o];
        lazy[o]=0;
    }
}
void update(int o,int l,int r,int ql,int qr,int val){
    if(ql<=l&&r<=qr){
        sum[o]+=val;
        lazy[o]+=val;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    if(ql<=mid)update(o<<1,l,mid,ql,qr,val);
    if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,val);
    pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
    
    if(ql<=l&&r<=qr){
        return sum[o];
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    int res=0;
    if(ql<=mid)res=query(o<<1,l,mid,ql,qr);
    if(qr>mid)res=max(res,query(o<<1|1,mid+1,r,ql,qr));
    return res;
}
int main(){
    while(cin>>n>>k)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            le[i]=pos[x];
            pos[x]=i;
        }
        int p=0;
        for(int s=1;s<=k;s++,p^=1)
        {
        clr(sum,0),clr(lazy,0);
            for(int i=1;i<=n;i++)
            {
                update(1,0,n,le[i],i-1,1);
                dp[p][i]=query(1,0,n,0,n);
                update(1,0,n,i,i,dp[p^1][i]);
            }
        }
        
        printf("%d
",dp[p^1][n]);
    }
}