少有的独自做出来的 *3000，还是很有成就感的！
集中注意力读题，首先注意到每一时刻牌数为 \(k\)，而牌的种类也为 \(k\)，如果实际牌的种类数小于 \(k\)，那么是很简单的情况，现在考虑实际牌的种类数等于 \(k\) 的情况。
观察过程，首先发现如果有相同的牌直接丢就行，过程中还会出现没有牌相同的情况，显然这种情况每个牌的数量为 \(1\)，启发我们使用 dp，设 \(f_i\) 表示已经考虑完 \(i\) 张牌且当前没有相同牌，能获得的最多硬币数。
首先呼之欲出的是 \(\mathcal{O}(n^2k^2)\) 的愚蠢做法。就是枚举我们删哪两张牌，再模拟出后面第一次出现没有相同牌状态的位置，并完成转移。
这样做是低效的。我们发现我们可以直接转移，在转移中变成判定问题，\(f_j\) 能转移到 \(f_i\)，当且仅当区间 \([i+1,j]\) 从当前状态继续操作完成后出现无相同牌状态，且中途一直有相同牌。注意到删相同牌不会改变奇偶性，而加入会，我们发现这个判定过程实际上是一个异或加入牌的过程，而一个区间能满足条件当且仅当存在两种牌出现个数为奇数，直接异或哈希即可。
还有一种很烦人的情况，就是永远都不会出现无相同牌的状态了，这时的答案与实际牌的种类数小于 \(k\) 的类似，他的答案就是 \(\sum_{i=1}^k \lfloor \frac{s_i}{2}\rfloor\)。\(s_i\) 表示第 \(i\) 种手牌的数量。然而，对于当前 \(f_i\) 的答案来说，\(s_i\) 是对于 \([i,n]\) 这个后缀算出来的，并且每个都会加一，因为当前每种牌各有一张。而这时我们要删除两张牌，显然我们因尽可能删除 \(s_i\) 为奇数的牌，因为这样不会减少答案。枚举牌对显然不优，但我们可以将判断转为简单计数。
然后还有个细节就是起点问题，直接模拟找起点就行了。
总时间复杂度 \(\mathcal{O}(n^2)\)。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define id(x, y) m * ((x) - 1) + (y)
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 1e3 + 5, P = 1e9;
constexpr double PI = acos (-1.0);
typedef unsigned long long ull;
inline int rd () {
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
if (ch == '-') f = -1;
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar ();
}
return x * f;
}
int qpow (int x, int y) {
int ret = 1;
for (; y; y >>= 1, x = x * x % P) if (y & 1) ret = ret * x % P;
return ret;
}
int n, k;
int a[N], b[N], f[N];
bitset <N> bit;
ull w[N];
unordered_map <ull, pii> mp;
unordered_map <ull, bool> mmp;
int s1[N][N], s[N];
int main () {
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
n = rd (), k = rd ();
rep (i, 1, n) a[i] = b[i] = rd ();
sort (b + 1, b + n + 1);
int kk = unique (b + 1, b + n + 1) - b - 1;
if (kk < k) {
rep (i, 1, n) ++ s[a[i]];
int sum = 0;
rep (i, 1, k) sum += s[i] / 2;
cout << sum;
return 0;
}
rep (i, 1, n) a[i] = lower_bound (b + 1, b + k + 1, a[i]) - b;
mt19937_64 rnd (time (0));
rep (i, 1, k) {
w[i] = rnd ();
rep (j, 1, i - 1) mp[w[i] ^ w[j]] = pii (i, j);
}
rrp (i, 1, n) {
ull now = 0;
rep (j, i, n) ++ s1[i][a[j]];
int s2[3] = {0, 0, 0}, s3[2] = {0, 0}, sum = 0;
rep (j, i, n) {
now ^= w[a[j]];
if (mp.find (now) != mp.end () && ! mmp[now]) {
pii p = mp[now];
mmp[now] = 1;
f[i - 1] = max (f[i - 1], f[j] + (j - i + 1) / 2 - 1);
int x = s1[i][p.first], y = s1[i][p.second];
if ((x & 1) ^ (y & 1)) ++ s2[1];
else if (x & 1) ++ s2[0]; else ++ s2[2];
}
}
now = 0;
rep (j, i, n) {
now ^= w[a[j]];
mmp[now] = 0;
}
rep (j, 1, k) sum += (s1[i][j] + 1) / 2, ++ s3[s1[i][j] & 1];
if (s3[1] * (s3[1] - 1) / 2 > s2[0]) f[i - 1] = max (f[i - 1], sum - 2);
if (s3[0] * s3[1] > s2[1]) f[i - 1] = max (f[i - 1], sum - 1);
if (s3[0] * (s3[0] - 1) / 2 > s2[2]) f[i - 1] = max (f[i - 1], sum);
}
int ans = -1;
rep (i, 1, n) {
if (bit[a[i]] == 1) bit[a[i]] = 0;
else bit[a[i]] = 1;
if (bit.count () == k) {
ans = max (ans, (i - k) / 2 + f[i]);
break;
}
}
if (ans == -1) {
rep (i, 1, n) ++ s[a[i]];
int sum = 0;
rep (i, 1, k) sum += s[i] / 2;
cout << sum; return 0;
}
cout << ans;
}