[Usaco2006 Nov]Corn Fields牧场的安排
2024-10-19 04:46:13
题目描述
Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。当然,FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮FJ算一下这个总方案数。
输入格式
第1行: 两个正整数M和N,用空格隔开
第2..M+1行: 每行包含N个用空格隔开的整数,描述了每块土地的状态。输入的第i+1行描述了第i行的土地。所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块地上不适合种草
输出格式
第1行: 输出一个整数,即牧场分配总方案数除以100,000,000的余数
虽然是暴搜的数据量,但暴搜的复杂度为O(2(122))......考虑优化,如果我们先填前排,再填后排,然后再填满前排可以等价于先填完再填后排。所以我们可以一排一排地搜,时间复杂度降到了O(12 * 2^12)。可以通过本题。
刚才口胡的。考虑一下标签上的算法(状压动规)?我们显然可以把某一排上种与不种的方案用二进制数来表示。设dp(i,j)表示第i排的种植情况为j的二进制数时的方案数,考虑可以转移过来的合法状态。
首先判断竖着没有连着的草坪。这是我们可以把上一排和当前这一排取交集,如果交集为空那么竖着没有连着的草坪。
再判断左右没有连着的草坪。先判断左边,如果我们把当前这一行右移一位,再与原来的状态取并集就可以判断了。右边类似。
最后判断有没有种到贫瘠的地方去。我们可以把当前行的贫瘠的地方也表示为二进制数,跟当前的种植情况的二进制数取交,如果交集为空就说明没有。
时间复杂度为O(N * 4^M),可以通过本题。
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 13
#define p 100000000
using namespace std;
int dp[maxn][1<<maxn],g[maxn];
int n,m;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int main(){
n=read(),m=read();
for(register int i=1;i<=n;i++){
for(register int j=0;j<m;j++) g[i]=(g[i]<<1)+read();
}
dp[0][0]=1;
for(register int i=1;i<=n;i++){
for(register int j=0;j<1<<m;j++) if((j&g[i])==j&&!((j&j<<1)||(j&j>>1))){
for(register int k=0;k<1<<m;k++){
if(!(k&j)) (dp[i][j]+=dp[i-1][k])%=p;
}
}
}
int ans=0;
for(register int i=0;i<(1<<m)-1;i++) (ans+=dp[n][i])%=p;
printf("%d\n",ans);
return 0;
}
然而你足够细心的话可以发现优化的地方:
我们其实对于每个j存不存在左右相邻的草坪都判断了N次。所以我们可以预处理出没有相邻草坪的二进制数,是一个不错的常数优化。
最新文章
- Sublime Text3 配置 NodeJs 环境
- android 中Activity的onStart()和onResume()的区别是什么
- CSS本页写样式
- SQLite中DML DDL DML命令的区别[转]
- Android WebView如何加载assets下的html文件
- mysql:The total number of locks exceeds the lock table size
- MySQl索引创建
- user-agent查询
- segue生命周期
- 一句话输出网站404页面,REFER及相关排序
- C#中通过类来继承两个接口,父类实例化接口中的方法,子类继承父类,调用方法
- JQuery基础知识(1)
- JVM问题诊断常用命令:jinfo,jmap,jstack
- LeetCode(40)-Merge Sorted Array
- spring3.1文档目录翻译
- java框架之springboot
- Thinkphp框架网站 nginx环境 访问页面access denied
- centos-rpm安装的mariadb,php52源码编译安装时注意点
- Linux中如何安装RAR
- codeforces 854C.Planning 【贪心/优先队列】
热门文章
- java 系统属性设置
- Spring Cloud Alibaba基础教程-Nacos(一)
- Barcodex帮助文档
- IDEA控制台打印程序内汉字乱码及txt文本乱码
- Weblogic命令执行漏洞(CVE-2018-2628)复现
- ArrayList哪种遍历效率最好,你真的弄明白了吗?
- [LeetCode]141. Linked List Cycle判断循环链表
- [LeetCode]367. Valid Perfect Square判断完全平方数
- openbmc编译错误汇总,持续更新,建议收藏
- SQL Server 数据库还原进度查看