Codeforces 834D The Bakery 【线段树优化DP】*

时间：2023-03-10 01:32:53
Codeforces 834D The Bakery 【线段树优化DP】*

Codeforces 834D The Bakery

LINK

题目大意是给你一个长度为n的序列分成k段，每一段的贡献是这一段中不同的数的个数，求最大贡献

是第一次做线段树维护DP值的题
感觉还可以，虽然看了一下这题是用线段树维护DP值

然后说思路
有一个很显然的思路是这样的:
dpi,j表示前i个数分成j段的最大贡献
dpi,j=max(dpk,j−1+calc(k+1,i))
然后我们就可以对于每一层j用线段树维护起来
然后就非常愉快地发现dp[i][p]只会从dp[i−1][p−1]之前的DP值进行转移
所以可以发现每次可以错位建立线段树

然后现在考虑怎么维护calc(k+1,i)
我们可以把一段区间的贡献拆成每个点的贡献
显然位置i的数会对左端点位置在pre[i]+1~i的所有点产生加一的贡献（因为考虑的右端点在i）
所以每次判断一下区间加区间求和就好了

 #include<bits/stdc++.h>

 using namespace std;

 #define N 350010

 int a[N],b[N];

 int dp[N][];

 int las[N],pre[N];

 int n,k;

 namespace Segment_Tree{

     #define MAXN N<<2

     #define LD (t<<1)

     #define RD (t<<1|1)

     int maxv[MAXN],add[MAXN];

     void pushup(int t){maxv[t]=max(maxv[LD],maxv[RD]);}

     void pushdown(int t){

         if(add[t]){

             maxv[LD]+=add[t],add[LD]+=add[t];

             maxv[RD]+=add[t],add[RD]+=add[t];

             add[t]=;

         }

     }

     void build(int t,int l,int r){

         if(l>r)return;

         add[t]=;

         if(l==r){maxv[t]=a[l];return;}

         int mid=(l+r)>>;

         build(LD,l,mid);

         build(RD,mid+,r);

         pushup(t);

     }

     void modify(int t,int l,int r,int L,int R){

         if(l>r)return;

         if(L<=l&&r<=R){maxv[t]++;add[t]++;return;}

         pushdown(t);

         int mid=(l+r)>>;

         if(R<=mid)modify(LD,l,mid,L,R);

         else if(L>mid)modify(RD,mid+,r,L,R);

         else{

             modify(LD,l,mid,L,mid);

             modify(RD,mid+,r,mid+,R);

         }

         pushup(t);

     }

     int query(int t,int l,int r,int L,int R){

         if(l>r)return ;

         if(L<=l&&r<=R)return maxv[t];

         pushdown(t);

         int mid=(l+r)>>;

         int ans=;

         if(R<=mid)ans=query(LD,l,mid,L,R);

         else if(L>mid)ans=query(RD,mid+,r,L,R);

         else ans=max(query(LD,l,mid,L,mid),query(RD,mid+,r,mid+,R));

         pushup(t);

         return ans;

     }

 };

 int main(){

     scanf("%d%d",&n,&k);

     for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

     sort(b+,b+n+);

     int tot=unique(b+,b+n+)-b-;

     for(int i=;i<=n;i++)a[i]=lower_bound(b+,b+tot+,a[i])-b;

     for(int i=;i<=n;i++)pre[i]=las[a[i]],las[a[i]]=i;

     for(int i=;i<=n;i++)dp[i][]=dp[i-][]+(int)(pre[i]==);

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

         for(int i=;i<=n;i++)a[i]=dp[i-][j-];

         Segment_Tree::build(,,n);

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

             Segment_Tree::modify(,,n,pre[i]+,i);

             dp[i][j]=Segment_Tree::query(,,n,,i);

         }

     }

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

     return ;

 }

相关文章