almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1037
分析:
我们假设男生为,女生为,我们只需保证任意区间和即可。
我们设表示前个男生,前个女生,前缀和最小为,最大为的方案数。
为了方便,我们采用正推的方法。
考虑能产生的贡献。
如果当前位置放一个男生,那么贡献就是(因为要考虑当前的前缀和来更新最小前缀和。)
如果当前位置放一个女生,那么贡献就是(因为要考虑当前的前缀和来更新最大前缀和。)
时间复杂度为
bzoj1037.cpp

← bzoj1034:[ZJOI2008]泡泡堂BNB bzoj1036:[ZJOI2008]树的统计Count →
 
comments powered by Disqus