CodeForces 834D The Bakery

题意：将N个数分成K块，每块的价值为不同数字的个数，现在求总价值最大。

题解：dp[i][j] 表示长度为j 且分成 i 块的价值总和。那么 dp[i][j] = max(dp[i-1][x]+右边的数的贡献) ( 1<=x < j )。如果每次都从左到右for过去一定会TLE，所以我们用线段树来优化这个查询的过程，并且用滚动数组消去第二维空间。

每次新扫到一个数T，他就会在上一个T的位置+1 --- 现在这个T的位置产生数目加一的贡献。

然后每次扫完一次，都用DP的值去重新建树。并且将DP的对应位置往右移动一位，这样下次访问这个位置就是 dp[i-1][x-1] + dp[1][x-j]的价值了。（j 为现在的位置）。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 typedef pair<int,int> pll;

 const int N = ;

 int dp[N], tree[N<<], lazy[N<<], pos[N], last[N];

 void Push_Up(int rt){

     tree[rt] = max(tree[rt<<], tree[rt<<|]);

 }

 void Push_Down(int rt){

     if(lazy[rt]){

         lazy[rt<<]+=lazy[rt];

         lazy[rt<<|]+=lazy[rt];

         tree[rt<<]+=lazy[rt];

         tree[rt<<|]+=lazy[rt];

         lazy[rt] = ;

     }

 }

 void Build(int l, int r, int rt){

     lazy[rt] = ;

     if(l == r){

         tree[rt] = dp[l-];

         return ;

     }

     int m = l+r >> ;

     Build(lson);

     Build(rson);

     Push_Up(rt);

 }

 void Update(int L, int R, int l, int r, int rt){

     if(L <= l && r <= R){

         lazy[rt]++;

         tree[rt]++;

         return;

     }

     int m = l+r >> ;

     Push_Down(rt);

     if(L <= m) Update(L,R,lson);

     if(m < R) Update(L,R,rson);

     Push_Up(rt);

 }

 int Query(int L, int R, int l, int r, int rt){

     if(L <= l && r <= R) return tree[rt];

     int ans = ;

     int m = l+r >> ;

     Push_Down(rt);

     if(L <= m) ans = max(ans, Query(L,R,lson));

     if(m < R) ans = max(ans, Query(L,R,rson));

     return ans;

 }

 int main(){

     memset(pos, , sizeof(pos));

     memset(last, , sizeof(last));

     int n, k, t;

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

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

         scanf("%d",&t);

         last[i] = pos[t] + ;

         pos[t] = i;

     }

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

         Build(,n,);

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

             Update(last[j],j,,n,);

             dp[j] = Query(,j,,n,);

         }

     }

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

     return ;

 }

巴特西

CodeForces 834D The Bakery

最新文章

热门文章