题解

思路

把保留下来的元素按值从小到大排列。美丽条件等价于相邻两种值满足整除关系；整除具有传递性，因此最终保留的不同值构成一条整除链，重复值可以全部保留。

问题转化为求带权整除链的最大权值，其中数值 $x$ 的权值是它在数组中的出现次数。答案为 $n$ 减去最大链权。

做法

子任务 1：枚举保留子集

枚举下标子集，逐对检查保留元素是否互相可比，取合法子集的最大大小。时间复杂度为 $O(2^n n^2)$。

子任务 2：两两检查转移

把不同值升序排列。令 $dp[i]$ 表示以第 $i$ 个值结尾的最大链权，枚举所有 $j<i$；若 $value_i$ 能被 $value_j$ 整除，就用 $dp[j]$ 转移。时间复杂度为 $O(k^2)$，其中 $k$ 是不同值数。

子任务 3：枚举倍数

令 count[x] 为 $x$ 的出现次数，dp[x] 为以 $x$ 结尾的最大链权。按 $x$ 递增处理：

随后枚举 $x$ 的所有倍数 $y=2x,3x,\ldots$，执行

因为 $x\mid y$，该转移恰好把一条合法整除链接到 $y$。最终最大保留数为 $\max_x dp[x]$。

正确性证明

引理 1

一个多重集合是美丽的，当且仅当其所有不同值按升序排列后相邻值均满足前者整除后者。

证明：美丽数组中任意两值可比，升序后只能是较小值整除较大值，所以相邻值满足整除。反之，若相邻值依次整除，由整除的传递性，任意较小值都整除任意较大值，数组美丽。证毕。

引理 2

处理完数值 $x$ 后，dp[x] 等于以 $x$ 结尾的最大整除链所含元素数。

证明：所有能接到 $x$ 前面的值都是 $x$ 的真因子，且严格小于 $x$，它们在处理时已经把最优值传播到 $x$。取最大前驱后加上全部 count[x] 个相等元素，得到以 $x$ 结尾的最优链。证毕。

定理

算法输出最少删除数。

证明：由引理 2，$\max dp[x]$ 是最大可保留整除链权；由引理 1，这正是最大美丽子数组长度。删除其余 $n-\max dp[x]$ 个元素既可行又最少。证毕。

复杂度

设值域上界为 $M=2\times10^5$。倍数枚举总次数为 $O(M\log M)$：

• 每组时间复杂度：$O(M\log M+n)$；
• 空间复杂度：$O(M)$。