题解 P3643 【[APIO2016]划艇】
xht
2020-01-30 21:41:19
首先将区间离散化成若干个左闭右开的区间。
设 $f_{i, j}$ 表示考虑到 $a_i$，$a_i$ 在第 $j$ 个区间内的方案数。
枚举上一个在 $j$ 之前的位置 $a_k$ 转移。
设 $k + 1 \sim i$ 中有 $c$ 个位置可以选择第 $j$ 个区间，设第 $j$ 个区间的长度为 $l_j$，则方案数为 $\binom{l_j + c}{c}$。
需要前缀和优化，时间复杂度 $\mathcal O(n^3)$。
```cpp
const int N = 507;
int n, a[N], b[N], c[N*2], t;
modint f[N], g[N], ans;
int main() {
rd(n);
for (int i = 1; i <= n; i++)
rd(a[i]), rd(b[i]), c[++t] = a[i], c[++t] = ++b[i];
sort(c + 1, c + t + 1), t = unique(c + 1, c + t + 1) - (c + 1);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(c + 1, c + t + 1, a[i]) - c,
b[i] = lower_bound(c + 1, c + t + 1, b[i]) - c;
f[0] = 1;
for (int j = 1; j < t; j++) {
int l = c[j+1] - c[j];
g[0] = 1;
for (int i = 1; i <= n; i++) g[i] = g[i-1] * (l + i - 1) / i;
for (int i = n; i; i--)
if (a[i] <= j && j < b[i])
for (int c = 1, k = i - 1; ~k; k--) {
f[i] += g[c] * f[k];
if (a[k] <= j && j < b[k]) ++c;
}
}
for (int i = 1; i <= n; i++) ans += f[i];
print(ans);
return 0;
}
```