题目大意

给定 $n$ 张卡牌，每张卡牌有一个数字 $a_i$（$1 \leq a_i \leq n$）。游戏规则如下：

依次抽牌，可以选择将牌加入手牌或丢弃

可以随时计算手牌分数：如果手中有 $x$ 张相同的牌，获得 $x^{k/2}$ 分，然后清空手牌

手牌中的牌必须数字完全相同

求通过最佳策略能获得的最高分数。

关键观察

相同数字的牌必须一起计算：由于手牌中的牌必须数字相同，相同数字的牌应该放在一起考虑。

动态规划状态设计：设 $f[i]$ 表示处理完前 $i$ 张牌能获得的最大分数。

转移方程：对于第 $i$ 张牌，有两种选择：

不选这张牌：$f[i] = f[i-1]$

选这张牌，并与前面相同数字的若干张牌一起计算分数

斜率优化：对于每个数字，维护一个决策队列，使用单调队列优化转移。

算法细节

状态转移 对于数字 $c$，假设当前处理到第 $i$ 张牌，它是数字 $c$ 的第 $j$ 次出现。考虑从数字 $c$ 的第 $p$ 次出现的位置转移过来：

f[i]=max(f[i],f[p−1]+(j−p+1) ^k/2) 斜率优化 对于每个数字维护一个决策队列，队列中的决策满足斜率单调性。使用二分查找来维护队列的决策优势。

分数计算 根据 $k$ 的值不同：

$k = 2$：分数为 $x$

$k = 3$：分数为 $x^{1.5} = x\sqrt{x}$

$k = 4$：分数为 $x^2$

复杂度分析

时间复杂度：$O(n \log n)$，每个数字最多入队出队一次，每次二分查找 $O(\log n)$

空间复杂度：$O(n)$