CF833B The Bakery (线段树+DP)

题目大意：给你一个序列(n<=35000)，最多分不大于m块(m<=50)，求每个块内不同元素的数量之和的最大值

考试的时候第一眼建图，没建出来，第二眼贪心，被自己hack掉了，又随手写了个dp方程，感觉可以用splay维护，发现有区间操作并可取，又发现这个方程只能用线段树维护，然后只剩40min了我没调完，而且线段树打错了......

定义f[i][j]表示以第i个数为这个块的结尾，已经分了j块的答案的最大值

很明显 $f[i][j]=f[k][j-1]+sum(k+1,i)$ ，sum表示不同元素数量

对于每个元素，记录一个 $last[i]$ 表示数 i 上一次出现的位置，那么遍历到i的时候，能更新sum的位置只有 $last[i]$ 到i-1，线段树维护区间修改！

而最大 $f[k][j-1]+sum(k+1,i)$ ，线段树维护区间最大值！

算好空间，建立M颗线段树即可

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define ull unsigned long long

 #define il inline

 #define mod 905229641

 #define N 35100

 #define M 52

 #define il inline

 using namespace std;

 //re

 int n,m;

 int a[N],lst[N];

 int f[N][M];

 struct Seg{

     int ma[N<<],tag[N<<];

     il void pushup(int rt){ma[rt]=max(ma[rt<<],ma[rt<<|]);}

     il void pushdown(int rt){

         if(tag[rt])

             ma[rt<<]+=tag[rt],ma[rt<<|]+=tag[rt],

             tag[rt<<]+=tag[rt],tag[rt<<|]+=tag[rt],tag[rt]=;}

     void update(int L,int R,int l,int r,int rt,int w)

     {

         if(L>R) return;

         if(L<=l&&r<=R){ma[rt]+=w;tag[rt]+=w;return;}

         pushdown(rt);

         int mid=(l+r)>>;

         if(L<=mid) update(L,R,l,mid,rt<<,w);

         if(R>mid) update(L,R,mid+,r,rt<<|,w);

         pushup(rt);

     }

     int query(int L,int R,int l,int r,int rt)

     {

         if(L>R) return ;

         if(L<=l&&r<=R) {return ma[rt];}

         pushdown(rt);

         int mid=(l+r)>>,ans=;

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

         if(R>mid) ans=max(query(L,R,mid+,r,rt<<|),ans);

         pushup(rt);

         return ans;

     }

 }s[M];

 int main()

 {

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

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

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

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

         scanf("%d",&a[i]);

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

     {

         for(int j=;j<=m;j++)

             s[j-].update(lst[a[i]],i-,,n,,),

             f[i][j]=s[j-].query(,i-,,n,),

             s[j].update(i,i,,n,,f[i][j]);

         lst[a[i]]=i;

     }

     int ans=;

     for(int i=;i<=m;i++)

         ans=max(ans,f[n][i]);

     printf("%d\n",ans);

     return ;

 }

巴特西

CF833B The Bakery (线段树+DP)

最新文章

热门文章