洛谷P1879题解
2024-09-04 12:45:56
显然是个状压DP。
看数据范围,不难发现算法复杂度应该是 \(O(n\times 2^n \times 2^n)\) 。
显然第一个 \(n\) 是遍历每一行的土地。 后面两个 \(2^n\) ,想都不用想就知道是暴力枚举上一行和这一行的状态。
而枚举状态这个东西比较浪费时间,所以我们可以先不考虑土地是否肥沃,把每一行的可能分布先做出来。
我们设这一行的状态是 \(i\) ,那么, \(i\) 中不能有相邻的两个 \(1\) 。可以这样 ((i & (i << 1)) == 0) && ((i & (i >> 1)) == 0)
判断。
然后我们要开一个数组记录每一行那些位置能放。我们为方便,设 \(1\) 是能放 \(0\) 是不能放。那么当我们枚举到一个状态的时候,算一下 j & map[i]
,当 i & map[i] == j
时就说明 \(j\) 中每个 \(1\) 对应到 \(map_i\) 里面都是 \(1\) ,那么这个 \(j\) 就是成立的。
接下来我们要枚举上一行的状态,然后判断两行中是否存在一个位置使得上下都被选上,那么我们算一下 k & j
即可。如果他不等于零说明这个 \(k\) 和 \(j\) 不能匹配。如果他等于零那就累加答案即可。
注:\(i\) 是行号 \(j\) 是当前行的状态 \(k\) 是上一行的状态。
最新文章
- MySQL Cluster 7.3.5 集群配置参数优化(优化篇)
- javascript生成对象的三种方法
- xhprof学习笔记
- 《python核心编程》笔记——系统限制
- [POJ 1988] Cube Stacking (带值的并查集)
- emWin显示文本字符-【worldsing笔记】
- 在windows下的mysql使用
- RMAN-FORMAT-CONFIGURE及动态性能表
- perl HTML::TreeBuilder::XPath
- [LeetCode] Search in Rotated Sorted Array [35]
- OOP 创建对象的7种方式
- (转) QImage总结
- fis3+vue+pdf.js制作预览PDF文件或其他
- asp:GridView控件使用FindControl方法获取控件的问题
- Jupyter Notebook启动不会自动打开浏览器,每次都要自己打开浏览器输入网址
- Redis设置Key/value的规则定义和注意事项(附工具类)
- .Net WebRequest异步请求与WebClient异步请求
- hasura graphql-engine v1.0.0-alpha26 版本新功能
- ASP.NET与ASP.NET MVC 中Cache的总结
- zookeeper报错 JAVA_HOME is not set