P2943 [USACO09MAR]清理Cleaning Up

• 167通过
• 360提交
• 题目提供者 FarmerJohn2
• 评测方式 云端评测
• 标签 动态规划,动规,dp 枚举,暴力 递推 USACO 2009 高性能
• 难度 省选/NOI-
• 时空限制 1000ms / 128MB
• 提示：收藏到任务计划后，可在首页查看。

题意翻译

很久很久以前，约翰只会做一种食品；而现在约翰能给他的$N$ $(1 \leq N \leq 40000)$头奶牛供应$M$ $(1 \leq M \leq N)$种不同的食品。但奶牛们非常挑剔，$i$号奶牛只吃食品$P_i$ $(1 \leq P_i \leq M)$

每天，奶牛们按一定编号排队进自助餐厅用餐。不幸的是，这么多各类的食品会让清扫工作变得非常不方便。如果约翰在一次用餐中供应了$K$种食品，他之后就需要$K^2$的时间进行清扫。

为了减少清扫的时间，约翰决定把排好队的奶牛划分成若干组。每一组包含一段连续的奶牛。每一次，只让一组奶牛进入餐厅。这样，他可以让清扫所需的总用时变得最小。请计算这个最小用时。

样例解释：

如此划分：1\2\1\3\22\34343\1\4

题目描述

In the good old days, Farmer John served a boring cuisine comprising but a single type of cow food to his N (1 <= N <= 40000) prize dairy cows. Times change. Today he serves the herd a total of M (1 <= M <= N) different types of food (conveniently numbered 1..M).

The cows are picky. Cow i has a single food preference P_i (1 <= P_i <= M) and will eat only that favorite food.

Each day at feeding time FJ converts the barn into a tastefully lit cafeteria. The cows line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Farmer John is serving K different types of food, it takes him K*K units of time to clean the barn.

To save time, FJ serves the cows in contiguous groups from the line. After each group, he cleans up the barn and sets out the food for the next group (of course, he only sets out food that cows in the any given group will eat). Determine the minimum amount of total time FJ must spend cleaning the barn. Each group consists of the next contiguous group of cows from the line; each cow belongs to exactly one group; and the barn must be cleaned up after every group, including the last one.

输入输出格式

输入格式：

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: P_i

输出格式：

* Line 1: A single integer: the minimum amount of time FJ must spend cleaning the barn.

输入输出样例

输入样例#1： 复制
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

输出样例#1： 复制
11
`

说明

There are four types of food and thirteen cows in line. The first cow prefers type 1, the second type 2, the third type 1, etc.

The first four groups contain one cow each. The fifth group contains two cows who prefer food #2 (requiring one unit of time). The sixth group contains cows preferring foods 3, 4, 3, 4, 3 (and requires four units of time to clean). The last two groups contain one cow each. The total time is 11.

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。