首页 > 其他 > 详细

P3120 [USACO15FEB]牛跳房子(线段树优化$dp$($CDQ$分治))

时间:2019-08-23 09:42:04      阅读:126      评论:0      收藏:0      [点我收藏+]

${\color{cyan}{>>Question}}$

很容易想到朴素方程,令$f[i][j]$表示到$i$行$,$j$列的方案数

$$f[i][j] = \sum f[k][l]\;(k<i,l<j,a[k][l] \neq a[i][j])$$

但显然是$O(n^4)$的,其实这看起来就想二维偏序,但实际它有三个条件,可以$CDQ$分治(但我不会)

考虑吧方程换个形式,令$sum = \sum f[k][l]\;(k<i,l<j)$,$x = \sum f[k][l]\;(k<i,l<j,a[k][l] = a[i][j])$

$$f[i][j] = sum - x$$

(类似那道染色的思想)

P3120 [USACO15FEB]牛跳房子(线段树优化$dp$($CDQ$分治))

原文:https://www.cnblogs.com/mzg1805/p/11398123.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!