APIO2016划艇 离散化DP

[APIO2016]划艇 考虑一个大暴力：令$f_{i,j}$表示前$i$个，强制选$i$，选的数是$j$的答案 $$f_{i,j} = \sum_{a < i, b < j} f_{a,b}$$ 值域很大，离散化。为了方便表示，把区间表示为$[l,r)$的形式。 那么定义$f_{i,j}$表示前$i$个，选择了$[w_j,w_{j+1})$这段区间。 $$f_{i,j} = \sum_{a < i, b < j} f_{a,b} ?$$ $?$是一个数。把这个DP式子的含义记为，钦定了$a$位置选在$b$区间，$a$位置之前选的是$ < j $的，$a$位置之后选$j$区间或不选的方案数。 考虑$n$个数里选一些，再选一些$0$，排成非$0$位置递增序列的方案数。 $$\binom{n + m}{m}$$ 意思是说，我们把$n$个数和$m$个$0$放在一起，选$m$个出来。如果是选了第$i$个$0$，就把位置$i$方成$0$。剩下取出来的数字显然确定了放在哪里和怎么放。 $$f_{i,j} = \sum_{a < i, b < j} f_{i,j} \binom{w_{j+1} - w_j - 1 + k}{k}$$ 其中，$k$是有几个数可选区间包含当前考虑的区间。 其实这个方案数也可以直接算（范德蒙德卷积）： $$\sum_{i=0}^m \binom{n}{i} \binom{m}{i} = \binom{n+m}{n}$$ 前缀和优化一下就$O(n^3)$了