「CF743E 」Vladik and cards

upd（20200226）:对当时的一些笔误做了修改，并添加了一些内容 正解当然是 $\texttt{DP}$,在这里不在多说。 但是如果想不到 $\texttt{DP}$,在考场上又该怎么办呢？ 在这里提供一种切实可过的思路。 我们发现，当我们所要取的数的顺序确定，以及每个数要取多少个也确定的时候，那么这个时候整个序列的最优取法就已经被确定了。因为这个时候，肯定是越靠前越好。 比如1,2,2,1,1,2,2,如果我要取 1,2,2 显然应该取靠前的，即 **1,2,2**,1,1,2,2,而不会去取 1,2,2,1,**1,2,2**,这样显然是不够优秀的。 由于答案具有单调性，所以我们可以考虑二分每个数要取多少个，再枚举排列。 这样的时间复杂度为 $O(8! \cdot \log_2n)$ 但是我们刚刚的想法并没有考虑问题中的限制二，即任意两种数字的数量差不大于一。 这个也好办，在二分的时候，我们已经求出了各个数字的数量全部一样时的最优解 这个时候只需要再暴力枚举一下每个数的数量能不能加一，dfs一遍即可。 时间复杂度为 $O(8 \cdot 2^8)$ 注意，要实现这样的复杂度，还需要提前预处理一下每一个位置之后的每一种数，第 $i$ 个在什么位置，这样才能够做到 $O(1)$ 转移 代码十分好实现，就不贴出来了 总时间复杂度为 $O(8!\cdot8\cdot 2^8\cdot \log_2n)$。理论上是可以通过本题的。且由于数据的特性，即使是最强的数据该算法也无法跑满。所以请放心使用。 我还是把当年丑得要死代码贴出来吧： [这里是代码](https://www.luogu.com.cn/paste/g4sqnvfs)