题目链接: 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 结果记录一下即可.
代码:
1 #include <iostream>View Code
2 #include <stdio.h>
3 #define lson l, mid, rt << 1
4 #define rson mid + 1, r, rt << 1 | 1
5 using namespace std;
6
7 const int MAXN = 4e4 + 10;
8 int pre[MAXN], last[MAXN], a[MAXN];
9 int dp[50 + 10][MAXN], sum[MAXN << 2], lazy[MAXN << 2];
10
11 void push_up(int rt){
12 sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
13 }
14
15 void push_down(int rt){
16 if(lazy[rt]){
17 sum[rt << 1] += lazy[rt];
18 sum[rt << 1 | 1] += lazy[rt];
19 lazy[rt << 1] += lazy[rt];
20 lazy[rt << 1 | 1] += lazy[rt];
21 lazy[rt] = 0;
22 }
23 }
24
25 void build(int l, int r, int rt, int k){
26 lazy[rt] = 0;
27 if(l == r){
28 sum[rt] = dp[k][l - 1];//注意sum初始化为上一轮的dp结果,更新gel(l,m)时只能与dp[i-1][l-1]匹配,所以这里的l也要减一
29 return;
30 }
31 int mid = (l + r) >> 1;
32 build(lson, k);
33 build(rson, k);
34 push_up(rt);
35 }
36
37 void update(int L, int R, int value, int l, int r, int rt){
38 if(L <= l && R >= r){
39 lazy[rt] += value;
40 sum[rt] += value;
41 return;
42 }
43 push_down(rt);
44 int mid = (l + r) >> 1;
45 if(L <= mid) update(L, R, value, lson);
46 if(R > mid) update(L, R, value, rson);
47 push_up(rt);
48 }
49
50 int query(int L, int R, int l, int r, int rt){
51 if(L <= l && R >= r) return sum[rt];
52 push_down(rt);
53 int cnt = 0;
54 int mid = (l + r) >> 1;
55 if(L <= mid) cnt = max(cnt, query(L, R, lson));
56 if(R > mid) cnt = max(cnt, query(L, R, rson));
57 return cnt;
58 }
59
60 int main(void){
61 int n, k;
62 scanf("%d%d", &n, &k);
63 for(int i = 1; i <= n; i++){
64 scanf("%d", &a[i]);
65 pre[i] = last[a[i]];
66 last[a[i]] = i;
67 }
68 for(int i = 1; i <= k; i++){
69 build(1, n, 1, i - 1);
70 for(int j = i; j <= n; j++){
71 update(pre[j] + 1, j, 1, 1, n, 1);
72 dp[i][j] = query(1, j, 1, n, 1);
73 }
74 }
75 printf("%d\n", dp[k][n]);
76 return 0;
77 }