BZOJ 3939 [Usaco2015 Feb]Cow Hopscotch

发布于 2017-06-23  105 次阅读


题目链接: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})\)

 

 


一个非常弱的准退役OIER