令$f[i]$表示以i为结尾的答案最小值，则$f[i] = min \{f[j] + cnt[j + 1][i]^2\}_{1 \leq j < i}$，其中$cnt[j + 1][i]$表示$[j + 1, i]$内有几个不同的数
对于区间长度为$k$，则答案最大值就是$\sqrt{k}$，所以对于每个$i$我们其实只要枚举$\sqrt{i}$个值就好了
/**************************************************************
Problem: 1584
User: rausen
Language: C++
Result: Accepted
Time:112 ms
Memory:1120 kb
****************************************************************/ #include <cstdio>
#include <algorithm> using namespace std;
const int N = 4e4 + ;
const int MXlen = ; int n, m;
int a[N], f[N], seq[MXlen], now[MXlen];
int st, mxlen, nowlen; inline int read(); inline int sqr(int x) {
return x * x;
} int main() {
int i, j;
n = read(), m = read();
for (i = ; i <= n; ++i) a[i] = read();
for (mxlen = ; mxlen * mxlen <= n; ++mxlen);
--mxlen;
for (i = ; i <= n; ++i) {
f[i] = i;
for (st = , j = ; j <= nowlen; ++j)
if (seq[j] == a[i]) {
st = j;
break;
}
if (!st) {
if (nowlen != mxlen) {
seq[++nowlen] = a[i];
now[nowlen] = i;
} else {
for (j = ; j < nowlen; ++j)
seq[j] = seq[j + ], now[j] = now[j + ];
seq[nowlen] = a[i], now[nowlen] = i;
}
} else {
for (j = st; j < nowlen; ++j)
seq[j] = seq[j + ], now[j] = now[j + ];
seq[nowlen] = a[i], now[nowlen] = i;
}
for (j = nowlen; j >= ; --j)
f[i] = min(f[i], f[now[j - ]] + sqr(nowlen - j + ));
}
printf("%d\n", f[n]);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}