12/18
18:05
OI

[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个数和m0放在一起,选m个出来。如果是选了第i0,就把位置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)