CodeForces–833B--The Bakery（线段树&&DP）

B. The Bakery

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Some time ago Slastyona the Sweetmaid decided to open her own bakery! She bought required ingredients and a wonder-oven which can bake several types of cakes, and opened the bakery.

Soon the expenses started to overcome the income, so Slastyona decided to study the sweets market. She learned it's profitable to pack cakes in boxes, and that the more distinct cake types a box contains (let's denote this number as the value of the box), the higher price it has.

She needs to change the production technology! The problem is that the oven chooses the cake types on its own and Slastyona can't affect it. However, she knows the types and order of n cakes the oven is going to bake today. Slastyona has to pack exactly k boxes with cakes today, and she has to put in each box several (at least one) cakes the oven produced one right after another (in other words, she has to put in a box a continuous segment of cakes).

Slastyona wants to maximize the total value of all boxes with cakes. Help her determine this maximum possible total value.

Input

The first line contains two integers n and k (1 ≤ n ≤ 35000, 1 ≤ k ≤ min(n, 50)) – the number of cakes and the number of boxes, respectively.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ n) – the types of cakes in the order the oven bakes them.

Output

Print the only integer – the maximum total value of all boxes with cakes.

Examples

Input

4 1
1 2 2 1

Output

Input

7 2
1 3 3 1 4 4 4

Output

Input

8 3
7 7 8 7 7 8 1 7

Output

Note

In the first example Slastyona has only one box. She has to put all cakes in it, so that there are two types of cakes in the box, so the value is equal to 2.

In the second example it is profitable to put the first two cakes in the first box, and all the rest in the second. There are two distinct types in the first box, and three in the second box then, so the total value is 5.

题意：

给你一个数字串，将串分为k段，每段的值为不同数字的种类数，求所有段的值之和的最大值。

思路：

用DP来解，DP[i][j] 表示的是前i个分为j段可以获得的最大值

状态转移方程为：

DP[i][j]= { DP[k][j-1] + val[k+1][i] , j-1<=k<i }

val[k+1][i] 代表的是k+1到i段不同种类的个数

我们可以用线段树来快速求出这个val值，详见我的另一篇博客：http://www.cnblogs.com/liuzhanshan/p/7296128.html

如果按照这个状态转移方程不进行优化来解的话，需要三重循环，O（n^3）显然是不能接受的。

我们利用滚动数组的思想进行优化，

首先枚举分段数量（外层循环为j，内层循环为i）。DP[i]为进行到当前j时，dp[k][j] {j-1<=k<i} 的最大值

同时，利用线段树来维护当前DP[i]，具体操作为每次进行内循环之前，重建一次线段树，将i点更新为dp[i-1]（这里需要一个偏移量，具体原因见如何求val值及代码）

代码：

  1 /*
  2 * @FileName: D:代码与算法2017训练比赛CF#426-pro.cpp
  3 * @Author: Pic
  4 * @Date:   2017-08-16 19:51:14
  5 * @Last Modified time: 2017-08-16 21:57:55
  6 */
  7 
  8 #include<bits/stdc++.h>
  9 using namespace std;
 10 const int INFINITE = INT_MAX;
 11 const int MAXN=35000+30;
 12 const int MAXNUM = MAXN*4+30;
 13 struct SegTreeNode
 14 {
 15     int val;
 16     int addMark;//延迟标记
 17 }segTree[MAXNUM];//定义线段树
 18 
 19 /*
 20 功能：当前节点的标志域向孩子节点传递
 21 root: 当前线段树的根节点下标
 22 */
 23 void pushDown(int root)
 24 {
 25     if(segTree[root].addMark != 0)
 26     {
 27         //设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递
 28         //所以是 “+=”
 29         segTree[root*2+1].addMark += segTree[root].addMark;
 30         segTree[root*2+2].addMark += segTree[root].addMark;
 31         //根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元
 32         //素加上一个值时，区间的最小值也加上这个值
 33         segTree[root*2+1].val += segTree[root].addMark;
 34         segTree[root*2+2].val += segTree[root].addMark;
 35         //传递后，当前节点标记域清空，防止多次向下传递，造成数据错误
 36         segTree[root].addMark = 0;
 37     }
 38 }
 39 
 40 /*
 41 功能：线段树的区间查询
 42 root：当前线段树的根节点下标
 43 [nstart, nend]: 当前节点所表示的区间
 44 [qstart, qend]: 此次查询的区间
 45 */
 46 int query(int root, int nstart, int nend, int qstart, int qend)
 47 {
 48     //查询区间和当前节点区间没有交集
 49     if(qstart > nend || qend < nstart)
 50         return -1;
 51     //当前节点区间包含在查询区间内
 52     if(qstart <= nstart && qend >= nend)
 53         return segTree[root].val;
 54     //分别从左右子树查询，返回两者查询结果的较小值
 55     pushDown(root); //----延迟标志域向下传递（在向下递归之前，首先将延迟标志域向下传递）
 56     int mid = (nstart + nend) / 2;
 57     return max(query(root*2+1, nstart, mid, qstart, qend),
 58                query(root*2+2, mid + 1, nend, qstart, qend));
 59 
 60 }
 61 
 62 /*
 63 功能：更新线段树中某个区间内叶子节点的值
 64 root：当前线段树的根节点下标
 65 [nstart, nend]: 当前节点所表示的区间
 66 [ustart, uend]: 待更新的区间
 67 addVal: 更新的值（原来的值加上addVal）
 68 */
 69 void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
 70 {
 71     //更新区间和当前节点区间没有交集
 72     if(ustart > nend || uend < nstart)
 73         return ;
 74     //当前节点区间包含在更新区间内
 75     if(ustart <= nstart && uend >= nend)
 76     {
 77         segTree[root].addMark += addVal;
 78         segTree[root].val += addVal;    //最小值当然也加1
 79         return ;
 80     }
 81     pushDown(root); //延迟标记向下传递（在向下递归之前，首先将延迟标志域向下传递）
 82     //更新左右孩子节点
 83     int mid = (nstart + nend) / 2;
 84     update(root*2+1, nstart, mid, ustart, uend, addVal);
 85     update(root*2+2, mid+1, nend, ustart, uend, addVal);
 86     //根据左右子树的值回溯更新当前节点的值
 87     segTree[root].val = max(segTree[root*2+1].val, segTree[root*2+2].val);
 88 }
 89 int a[MAXN],last[MAXN],pre[MAXN];
 90 int dp[MAXN];
 91 void build(int root,int nstart,int nend)
 92 {
 93 	segTree[root].addMark=0;
 94 	if(nstart==nend){
 95 		segTree[root].val=dp[nstart-1];
 96 		return ;
 97 	}
 98 	int mid=(nstart+nend)/2;
 99 	build(root*2+1,nstart,mid);
100 	build(root*2+2,mid+1,nend);
101 }
102 int main(){
103 	//freopen("data.in","r",stdin);
104 	int n,k;
105 	scanf("%d%d",&n,&k);
106 		for(int i=1;i<=n;i++){
107 			scanf("%d",&a[i]);
108 			pre[i]=last[a[i]];
109 			last[a[i]]=i;
110 		}
111 		for(int j=1;j<=k;j++){
112 			build(0,0,n);
113 			for(int i=1;i<=n;i++){
114 				update(0,0,n,pre[i]+1,i,1);
115 				dp[i]=query(0,0,n,0,i);
116 			}
117 		}
118 		printf("%d
",dp[n]);
119     return 0;
120 }

View Code