Codeforces Round #426 (Div. 2)

题目链接：http://codeforces.com/contest/834/problem/D

题意：给定一个长度为n的序列和一个k，现在让你把这个序列分成刚好k段，并且k段的贡献之和最大。对于每一段的贡献为该段有多少个不同的数字。

思路：考虑dp, dp[k][i]表示前i个数切k段的答案，那么dp[k][i]=max(dp[k-1][j]+color(j+1,i)) [1<=j<i], [color(l,r)表示区间[l,r]有多少个不同的数字] ,由于第k行的dp值只会影响到k+1行的dp值，所以我们可以把k这一维忽略掉。考虑转移dp[k][i+1],新增加的i+1这个点会影响到[pre[a[i]]+1,i]这段区间+1。

ftiasch的题解

我们在建线段树的时候，树上的结点(结点表示的区间为[l,r])维护的是g[k](即dp[k-1][r-1])，然后就是区间加和区间最大值了。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <queue>

#include <cstring>

#include <algorithm>

#include <map>

#include <string>

#include <bitset>

using namespace std;

typedef long long LL;

const int MAXN =  + ;

int n,k,pre[MAXN],dp[MAXN];

struct Color{

    int val,l,r;

}c[MAXN];

//Segment Tree

#define L(x)(x<<1)

#define R(x)(x<<1|1)

struct Node{

    int l,r,Lazy,maxval;

    Node(int _l=,int _r=,double _val=){

        l=_l; r=_r; maxval=_val;

    }

}Seg[MAXN*];

void pushUp(int k){

    Seg[k].maxval=max(Seg[L(k)].maxval,Seg[R(k)].maxval);

}

void pushDown(int k){

    if(Seg[k].Lazy){

        Seg[L(k)].Lazy+=Seg[k].Lazy;

        Seg[L(k)].maxval+=Seg[k].Lazy;

        Seg[R(k)].Lazy+=Seg[k].Lazy;

        Seg[R(k)].maxval+=Seg[k].Lazy;

        Seg[k].Lazy=;

    }

}

void Build(int st,int ed,int k){

    Seg[k].l=st; Seg[k].r=ed; Seg[k].Lazy=;

    if(st==ed){

        Seg[k].maxval=dp[st-];

        return;

    }

    int mid=(st+ed)>>;

    Build(st,mid,L(k)); Build(mid+,ed,R(k));

    pushUp(k);

}

void Modify(int st,int ed,int k,int val){

    if(Seg[k].l==st&&Seg[k].r==ed){

        Seg[k].maxval+=val;

        Seg[k].Lazy+=val;

        return;

    }

    pushDown(k);

    if(Seg[L(k)].r>=ed){

        Modify(st,ed,L(k),val);

    }else if(Seg[R(k)].l<=st){

        Modify(st,ed,R(k),val);

    }else{

        Modify(st,Seg[L(k)].r,L(k),val); Modify(Seg[R(k)].l,ed,R(k),val);

    }

    pushUp(k);

}

int Query(int st,int ed,int k){

    if(Seg[k].l==st&&Seg[k].r==ed){

        return Seg[k].maxval;

    }

    pushDown(k);

    int res;

    if(Seg[L(k)].r>=ed){

        res=Query(st,ed,L(k));

    }else if(Seg[R(k)].l<=st){

        res=Query(st,ed,R(k));

    }else{

        res=max(Query(st,Seg[L(k)].r,L(k)),Query(Seg[R(k)].l,ed,R(k)));

    }

    pushUp(k);

    return res;

}

int main(){

#ifdef kirito

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

#endif

    while(~scanf("%d%d",&n,&k)) {

        memset(pre,,sizeof(pre));

        for(int i=;i<=n;i++){

            scanf("%d",&c[i].val);

            c[i].r=i; c[i].l=pre[c[i].val]+; pre[c[i].val]=i;

        }

        for(int i=;i<=n;i++){

            dp[i]=dp[i-]+(c[i].l==?:);

        }

        for(int j=;j<=k;j++){

            Build(,n,);

            for(int i=;i<=n;i++){

                Modify(c[i].l,c[i].r,,);

                dp[i]=Query(,i,);

            }

        }

        printf("%d\n",dp[n]);

    }

    return ;

}

巴特西

Codeforces Round #426 (Div. 2) - D

最新文章

热门文章