APIO2016 划艇

给定 (n) 个数，每个点的取值为 ([a_i,b_i])，每个数可以选/不选，选之后需要确定其权值，求多少种选数方案使得其单调不降。

( m Sol:)

先考虑一个 (mathcal O(nw)) 的做法，(f_{i,j}=[a_ile jle b_i]sum_{k<j} f_{i-1,k}+f_{i-1,j})

接下来有两种做法：

先将段进行离散化，每个权值当作 ([A,B)) 这样的一个段，设 (f_{i,j,k}) 表示当前考虑到第 (i) 个位置，当前权值选在第 (j) 段内，当前段选了 (k) 个不同的数的方案数。

然后直接转移即可，复杂度 (mathcal O(n^3))

另一种做法是，考虑将区间划分为若干个 ([l,r)) 的并，那么对于每一段区间，决策是一个 (i) 次多项式。

可以考虑直接维护 (n) 个点值，转移直接插值即可，对于每个点都需要插值一次，复杂度为 (mathcal O(n^3))