cf834D(dp+线段树区间最值,区间更新)

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

题意: 每个数字代表一种颜色, 一个区间的美丽度为其中颜色的种数, 给出一个有 n 个元素的数组, 问将其分成 k 个区间, 问 k 个区间的美丽度和最大为多少 .

思路: dp + 线段树区间更新, 区间最值

用 dp[i][j] 存储前 j 个元素分成 i 个区间的最大美丽度和为多少, 那么动态转移方程式为:

dp[i][j] = max(dp[i - 1][k] + gel(k + 1, n)), 其中 i <= k <= n, gel(k + 1, n) 表示区间 [k + 1, n] 的美丽度为多少 .

可以用线段树来维护 dp[i -1][k] + gel(k + 1, n) 的值, 这部分和 http://www.cnblogs.com/geloutingyu/p/7298049.html里面的线段树用法是一样的. 建树时将 sum 初始化为上一轮 dp 的结果. 再遍历 [i, m] 并将 dp 结果记录一下即可.

代码:

 #include <iostream>

 #include <stdio.h>

 #define lson l, mid, rt << 1

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

 using namespace std;

 const int MAXN = 4e4 + ;

 int pre[MAXN], last[MAXN], a[MAXN];

 int dp[ + ][MAXN], sum[MAXN << ], lazy[MAXN << ];

 void push_up(int rt){

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

 }

 void push_down(int rt){

     if(lazy[rt]){

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

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

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

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

         lazy[rt] = ;

     }

 }

 void build(int l, int r, int rt, int k){

     lazy[rt] = ;

     if(l == r){

         sum[rt] = dp[k][l - ];//注意sum初始化为上一轮的dp结果,更新gel(l,m)时只能与dp[i-1][l-1]匹配,所以这里的l也要减一

         return;

     }

     int mid = (l + r) >> ;

     build(lson, k);

     build(rson, k);

     push_up(rt);

 }

 void update(int L, int R, int value, int l, int r, int rt){

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

         lazy[rt] += value;

         sum[rt] += value;

         return;

     }

     push_down(rt);

     int mid = (l + r) >> ;

     if(L <= mid) update(L, R, value, lson);

     if(R > mid) update(L, R, value, rson);

     push_up(rt);

 }

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

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

     push_down(rt);

     int cnt = ;

     int mid = (l + r) >> ;

     if(L <= mid) cnt = max(cnt, query(L, R, lson));

     if(R > mid) cnt = max(cnt, query(L, R, rson));

     return cnt;

 }

 int main(void){

     int n, k;

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

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

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

         pre[i] = last[a[i]];

         last[a[i]] = i;

     }

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

         build(, n, , i - );

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

             update(pre[j] + , j, , , n, );

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

         }

     }

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

     return ;

 }

巴特西

cf834D(dp+线段树区间最值,区间更新)

最新文章

热门文章