实数域上的DP？——[AGC020F] Arcs on a Circle

# 实数域上的DP？——[AGC020F] Arcs on a Circle 有点没搞懂。 --- 注意到线段长度为整数，即li和ri的小数部分一定相同 而判断两个线段是否相交只会用到l和r的相对大小关系，所以可以对小数部分离散化 然后就可以 dp 了。 先断环为链，$n!$ 暴力枚举小数部分相对大小，离散化以后一共会有 $nC$ 个离散点。 设 $f[i][j][S]$，当前考虑到了左端点在 $i$ 的线段，覆盖的最远点在 $j$，已经放置的线段集合为$S$，对应的放置方案数。 由于每个端点对应的线段只有一个，所以转移是 $\mathcal O(1)$ 的。 每条线段出现在特定位置的概率是 $\frac 1C$，因为圆可以转，钦定第一条线段为上端，那么一种局面的概率为$\frac {1}{C^{n-1}}$。 由于有 $n!$ 种相对大小关系，每种关系概率相同（等价性），最后还要除以 $n!$ 复杂度 $O(n!2^nnC)$。 --- 1. 所以实数域上 DP，一定是分析性质，将其离散化为正整数域。并且考虑一些相对大小关系 2. 在实数域上，随机到一个确切点（指定点）的概率为 $0$ ，所以不用考虑两个线段小数部分相同的情况。 3. 用若干区间覆盖为全集是一个指数复杂度问题。