BZOJ 3939 [Usaco2015 Feb]Cow Hopscotch


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3939

题意:网格图,格子有颜色,从一个格子出发只能向严格右下方走不一样颜色的格子,问 (1,1) 到 (n,m) 的不同路径数


考虑 DP,严格向右下走即严格从左上转移来,再减去颜色一样的情况即可,那么朴素的 DP 式是这样的

$$f_{i,j}=sum_{i-1,j-1}-\sum_{a=1}^{i-1}\sum_{b=1}^{j-1}(f_{a,b}*[col_{a,b}=col_{i,j}])$$

其中\(col\) 表示颜色,\(sum\) 表示\(f\) 的前缀和

复杂度的瓶颈在于式子的后一半如何统计,对每个颜色建立一个动态开点的线段树即可,详见代码

时空复杂度均为\(O(nmlog_{nm})\)

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3939 [Usaco2015 Feb]Cow Hopscotch


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , ,