抽象复杂度小记

$O(2^{n/2})$，$O(3^{n/3})$ 之类。

P5972

长为 $n$ 的序列。

对每个 $k\in [1,n]$，求长度为 $k$ 的子序列的最小逆序对数。

$n\le 40$。

选完前 $i$ 个时，只关心 $a_{i+1\sim n}$ 的 $n-i$ 个数排序后的每个间隔选了几个数。状态数为 和为 $n$ 的一些数的乘积 能取到的最大值。在每段为 $e$ 取得最值，对于整数，在每段为 $3$ 时取到最值。复杂度 $O(n^2{3}^{n/3})$。

CF1958I

两棵大小为 $n$ 的有根树。

可以进行如下操作：选择其中一棵树的一个非根节点 $x$，将 $x$ 的所有儿子和 $x$ 的父亲连边，然后删去 $x$ 以及与 $x$ 连接的边。

求最小的操作次数，使得，对于两棵树中编号相同的两个点，它们的父亲编号也相同。

$n\le 40$。

有个很高妙的做法，最后发现正解很蠢。

设 $d{p}_u$ 表示考虑了第一颗树中 $u$ 的子树且选了 $u$ 点，最多能保留几个点。

P10360