CF833B The Bakery

不久前，Slastyona the Sweetmaid 决定开设自己的面包店！她买齐了所需的原料，还有一台可以烘焙多种蛋糕的奇妙烤箱，并开张了面包店。 很快，开支开始超过收入，于是 Slastyona 决定研究甜点市场。她了解到，将蛋糕装入盒子会更有利可图，而且每个盒子里不同种类蛋糕越多（我们将这个数量称为盒子的价值），价格就越高。 她需要改变生产技术！问题在于，烤箱会自行决定蛋糕的种类，Slastyona 无法干预。然而，她知道今天烤箱将要依次烘烤出 $n$ 个蛋糕的类型和顺序。今天，Slastyona 必须准确地用 $k$ 个盒子来打包这些蛋糕，并且每个盒子内必须放入若干（至少一个）连续烘焙出来的蛋糕（换句话说，每个盒子包含一段蛋糕的连续区间）。 Slastyona 希望最大化所有盒子的总价值。请你帮她求出所有盒子的最大可能总价值。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 35000$，$1 \leq k \leq \min(n, 50)$）——蛋糕的数量以及盒子的数量。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$（$1 \leq a_{i} \leq n$）——按照烤箱生产顺序排列的蛋糕类型。

输出唯一一个整数，表示所有盒子中的蛋糕最大可能的总价值。

在第一个样例中，Slastyona 只有一个盒子。她必须把所有蛋糕都放进这个盒子里，因此这个盒子有两种类型，价值为 $2$。 在第二个样例中，最优策略是将前两个蛋糕放入第一个盒子，其余的都放进第二个盒子。则第一个盒子有两种类型，第二个盒子有三种类型，因此总价值为 $5$。 由 ChatGPT 5 翻译