题目大意：

给你一串数（n<35000）,让你把他们分成 k（k<50）段，每一段的值定义为这一段里不同数字的个数。现在让你求出一种划分方式，使得这 k 个区间段的值的和最大。

分析：

定义状态：

dp[ i ][ j ] 表示把前 j 个分成 i 份能得到的最大值；dif[ i ][ j ] 表示区间 [ i , j ] 里面不同的数的个数。

状态转移方程：

dp[i][j]=maxdp[i−1][k]+dif[k+1][j]|0<=k<=j

关于优化时间复杂度：

如此看来时间复杂度应该是O(n^2 k)，这么搞怕是要超时。所以要想办法利用之0前得到的结果。
对于每一次处理分成 k 段时求解 dp[ k ][ k ] ~ dp[ k ][ n ] 的值，创建一颗线段树，定义其每个节点 tree[ i ] 表示的意义为：第 i 个点到第 j 个点的区间中不同的数的个数+dp[ k-1 ][ i-1 ]。这样就在一边维护 tree[ j ] 的同时就确定了 dp[ k ][ j ] 的值。

代码：

#include<bits/stdc++.h>
#define MAXN 35050
using namespace std;

int tree[MAXN<<2];//记录a[i]到a[j]的最大值。
int n,k;
int a[MAXN];
int pre[MAXN];//pre[i]表示a[i]的前一个和他相同的数的下标。
int last[MAXN];
int temp[MAXN];
int lazy[MAXN<<2];
int dp[60][MAXN]={0};

void Push_up(int x)
{
    tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt]=temp[l];
        return;
    }
    int mid=(l+r)>>1;
    Build( l , mid , rt<<1 );
    Build( mid+1 , r , rt<<1|1 );
    Push_up( rt );
}
void Push_down(int rt)
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        tree[rt<<1]+=lazy[rt];
        tree[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }

}
void Add_interval(int L,int R,int C,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        tree[rt]+=C;
        lazy[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    Push_down(rt);
    if(L<=mid)Add_interval(L,R,C,l,mid,rt<<1);
    if(R>mid)Add_interval(L,R,C,mid+1,r,rt<<1|1);
    Push_up(rt);
}
int Qurey_interval(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)return tree[rt];
    int mid=(r+l)>>1;
    Push_down(rt);
    int ans=0;
    if(L<=mid)ans=max(ans,Qurey_interval(L,R,l,mid,rt<<1));
    if(R>mid)ans=max(ans,Qurey_interval(L,R,mid+1,r,rt<<1|1));
    Push_up(rt);
    return ans;
}
void Add_point(int L,int C,int l,int r,int rt)
{
    if (l==r)
    {
        tree[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    Push_down(rt);
    if (L<=mid)
        Add_point(L,C,l,mid,rt<<1);
    else
        Add_point(L,C,mid+1,r,rt<<1|1);
    Push_up(rt);
}

int main()
{
    scanf("%d%d",&n,&k);
    memset(last,0,sizeof(last));
    memset(pre,0,sizeof(pre));
    memset(temp,0,sizeof(temp));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pre[i]=last[a[i]];
        last[a[i]]=i;
    }
    for(int i=1;i<=k;i++)
    {
        memset(tree,0,sizeof(tree));
        memset(lazy,0,sizeof(lazy));
        Build(1,n,1);

        for(int j=1;j<=n;j++)
        {
            Add_interval( pre[j]+1 , j , 1 , 1 , n , 1 );
            if(i<=j)
            {
                dp[i][j]=Qurey_interval(1,j,1,n,1);//取 [ 1 , j ] 的最大值。-+
                temp[j+1]=dp[i][j];
            }


            //cout<<temp[j]<<" ";
        }
        //cout<<endl;
    }
    int ans=0;
    printf("%d\n",dp[k][n]);
}