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

· · 个人记录

考虑dp

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

$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}