P3643 [APIO2016] 划艇 （学习笔记）

考虑dp

由于值域非常大，考虑离散化

$f_{i,j}$ 表示第i个学校，数量在第j个区间内

$sum_{i,j}$ 表示值域[0,j]的非0数递增的长度为i序列有几个，且序列不全为0

因为在同一段的学校一定是连成一片的，考虑枚举后缀

所以$f_{i,j}=\sum_{k=1}^{i-1}\sum_{v=1}^{j-1}f_{k,v}*sum_{i-k+1,len_j}$

O(n^4)

考虑优化

令$g_{i,j}=\sum_{k=1}^jf_{i,k}$

所以$f_{i,j}=sum_{i-k+1,len_j}*\sum_{k=1}^{i-1}g_{k,j-1}$

为O(n^3)

考虑如何计算sum

sum等价于 $0，0，0，0……0（i个0），1，2，3，……j$

中选i个

去第k个0代表第k个数为0 又因为第i个数不为0 $sum_{i,j}=C^{i}_{i+len{j}-1}$