#P1584. [Usaco2009 Mar]Cleaning Up 打扫卫生

    ID: 599 传统题 1000ms 256MiB 尝试: 752 已通过: 382 难度: 6 上传者: 标签>CF2100提高线性 DP枚举较小维度滑动窗口消除被支配候选动态规划:背包DP数据结构:分块Gold

[Usaco2009 Mar]Cleaning Up 打扫卫生

题目描述

有 nn 头奶牛,每头那牛都有一个标号 pip_i,现在 FJ 要把这些奶牛分成若干段,定义每段的不和谐度为:若这段里有 kk 个不同的数,该段的不和谐度即为 k2k^2,总的不和谐度就是所有段的不和谐度的总和。请你计算分段之后的最小不和谐度。

输入格式

  • 第一行:两个整数 n,mn,m。

  • 第 2∼n+12\sim n+1 行:nn 个整数,代表每个奶牛的编号。

输出格式

  • 第一行:一个整数,代表最小不和谐度
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
11

数据规模与约定

对于 100%100\% 的数据,1≤pi≤m≤n≤400001 \le p_i \le m \le n \le 40000。

题目来源

Usaco2009 Mar Gold