题目描述
https://www.luogu.com.cn/problem/CF1093F
简要题意：给定一个长为 $n$ 的序列 $a$，需要将 $a$ 划分成若干段，使得所有段的代价和最小，一段的代价定义为这一段中不同的数字的种数的平方
$n\le 40000$
Solution
容易发现 $dp$ 的转移并不满足决策单调性，所以我们要从别的方向出发
注意到答案的上界为 $n$，那么一个长度为 $len$ 的区间的不同数字的种数不能超过 $\sqrt len$，否则一定不优
另外还能发现 $f$ 一定单调不降
那么我们可以考虑记录以 $i$ 为终点，区间有 $k$ 种不同数字的最靠左的端点
$k$ 只需要记录到 $\sqrt n$ 即可，且随着 $i$ 的增加可以均摊 $O(1)$ 转移
所以总的时间复杂度就是 $O(n\sqrt n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <cmath>
#define maxn 40010
#define maxs 210
#define INF 1000000000
using namespace std;
int n, m, a[maxn];
int p[maxs], cnt[maxs][maxn], sum[maxs];
int f[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; int N = sqrt(n);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= N; ++i) p[i] = 0;
fill(f, f + maxn, INF); f[0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= N; ++j) {
if (++cnt[j][a[i]] == 1) ++sum[j];
while (sum[j] > j) {
if (--cnt[j][a[p[j] + 1]] == 0) --sum[j];
++p[j];
}
f[i] = min(f[i], f[p[j]] + sum[j] * sum[j]);
}
cout << f[n] << "\n";
return 0;
}
|