P2943 [USACO09MAR] Cleaning Up G

在过去的好日子里，农夫约翰只为他的 N ($1 \leq N \leq 40000$) 头优质奶牛提供一种单一类型的牛饲料。时光流逝，如今他为牛群提供总共 M ($1 \leq M \leq N$) 种不同类型的食物（方便地编号为 1 到 M）。 奶牛们很挑剔。奶牛 i 只有一个食物偏好 $P_i$ ($1 \leq P_i \leq M$)，并且只吃那种最喜欢的食物。 每天喂食时间，FJ 将谷仓改造成一个灯光优雅的自助餐厅。奶牛们按照之前提到的方便索引编号排队进入餐厅。 不幸的是，由于食物种类繁多，事后清理工作非常耗时。如果农夫约翰提供 K 种不同类型的食物，他需要花费 $K \times K$ 单位的时间来清理谷仓。 为了节省时间，FJ 将奶牛按连续的组来喂食。每组之后，他清理谷仓并为下一组准备食物（当然，他只准备给定组中的奶牛会吃的食物）。请确定 FJ 清理谷仓所需的最少总时间。每组由队列中下一个连续的奶牛组组成；每头奶牛只属于一个组；每组之后，包括最后一组，谷仓都必须清理。

\* 第 1 行：两个用空格分隔的整数：N 和 M \* 第 2 行到第 N+1 行：第 i+1 行包含一个整数：$P_i$

\* 第 1 行：一个整数：FJ 清理谷仓所需的最少时间。

有四种类型的食物和十三头奶牛排队。第一头奶牛喜欢类型 1，第二头喜欢类型 2，第三头喜欢类型 1，等等。 前四组每组包含一头奶牛。第五组包含两头喜欢食物 #2 的奶牛（需要一单位时间）。第六组包含喜欢食物 3、4、3、4、3 的奶牛（需要四单位时间清理）。最后两组每组包含一头奶牛。总时间是 11。 （由 ChatGPT 4o 翻译）