BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排 状压DP
Description
Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。当然,FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮FJ算一下这个总方案数。
Input
* 第1行: 两个正整数M和N,用空格隔开
* 第2..M+1行: 每行包含N个用空格隔开的整数,描述了每块土地的状态。输入的第i+1行描述了第i行的土地。所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块地上不适合种草
Output
* 第1行: 输出一个整数,即牧场分配总方案数除以100,000,000的余数
Sample Input
1 1 1
0 1 0
Sample Output
解题思路 :以样例数据第一行为例,三个格子都可以放牧,即每个格子都可以选择放,或不放。再考虑附加条件“相邻格子不可同时放牧”,那么我们可以列出单看第一行时的所有可行状态如下(1代表放牧,0代表不放牧)
编号 | 状态 |
1 | 0 0 0 |
2 | 0 0 1 |
3 | 0 1 0 |
4 | 1 0 0 |
5 | 1 0 1 |
由此,可将表中的状态看作二进制表示,那么,只需将每种状态转化为相应的十进制数,即可只用一个数字,就能表示某一种状态,如下表:
编号 | 二进制 | 十进制 |
1 | 0 0 0 | 0 |
2 | 0 0 1 | 1 |
3 | 0 1 0 | 2 |
4 | 1 0 0 | 4 |
5 | 1 0 1 | 5 |
这种用一个数来表示一组数,以降低表示状态所需的维数的解题手段,就叫做状态压缩。
至此我们看到,在只考虑第一行的时候,有5种可行的放牧方案,但这只是我们要做的第一步。接下来要将第二行纳入考虑:
首先思考:纳入第二行后,会对当前问题造成什么样的影响?
答案还是那句话:“ 相邻格子不可同时放牧 ”!
也就是说,不止左右相邻不可以,上下之间也不能存在相邻的情况。
首先观察第二行,只有中间的格子可以放牧,那么我们的状态表格就可以相对简单些了~如下:
编号 | 二进制 | 十进制 |
1 | 0 0 0 | 0 |
2 | 0 1 0 | 2 |
只有两种可行状态,那么我们不妨一个一个来考察:
1、当第二行的状态为编号1时,第二行的三个格子都没有放牧,那么就不会与第一行的任何情况有冲突,第一行的5种方案都可行,即:第二行选用编号1的状态时,结合第一行,可得到5种可行的放牧方案;
2、当第二行的状态为编号2时,第二行中间的格子已经放牧了,那么第一行中间的格子就不可以放牧。看表2,发现其中第3种状态与当前第二行冲突,那么第一行只有4种方案是可行的,即:第二行选用编号2的状态时,结合第一行,可得到4种可行的放牧方案;
那么,在样例数据给出的情况下,我们的最终答案即为5+4=9;
通过对样例数据的分析即可以发现不同状态之间的关系:
以 dp[i][state(j)] 来表示对于 前i行 , 第i行 采用 第j种状态 时可以得到的 可行方案总数!
例如:回头看样例数据,dp[2][1]即代表第二行使用第2中状态(0 1 0)时可得的方案数,即为4;
那么,可得出状态转移方程为:
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)] (kn即为上一行可行状态的编号,上一行共有n种可行状态)
最终ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)]; (kn即为 最后一 行 (第m行) 可行状态的编号)
AC代码:
#include<stdio.h>
#include<string.h>
const int mod = ;
int n,m,tot,v[],ans;//v[i]//第i行整行的情况
int dp[][],s[];//dp对于前i行,每行有前j种可能状态时的解
//s[i]存储每行所有可行的状态
int main( )
{
int a;
while(scanf("%d%d",&n,&m)!=EOF)
{
tot=ans=;
memset(dp,,sizeof(dp));
memset(s,,sizeof(s));
memset(v,,sizeof(v)); for(int i= ; i<<<m ; i++)
if((i&(i<<))==)///记录不相邻的状态
s[++tot]=i;
for(int i= ; i<=n ; i++)
{
for(int j= ; j<=m ; j++)
{
scanf("%d",&a);
if(a==)
v[i]+=<<j-;//相反方式存储
}
}
dp[][]=;
for(int i= ; i<=n ; i++)
{
for(int j= ; j<=tot ; j++)//判断第i行 假如按状态j放牛的话行不行
{
if(s[j]&v[i])//剪枝 判断上一行与其状态是否满足
continue;
for(int k= ; k<=tot ; k++)
{
if(s[j]&s[k])
continue;
dp[i][j]=(dp[i][j]+dp[i-][k])%mod;
}
}
} for(int i=;i<=tot;i++)
{
if(s[i]&v[n]) continue;
ans=(ans+dp[n][i])%mod;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- [LeetCode] Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历
- x64内联汇编注意点
- .net学习笔记---xml基础知识
- Oracle SQL优化一(常见方法)
- linux NFS服务器安装与配置 思路
- JAVA Socket:文件传输
- (链接保存)CentOS 6.6下yum快速升级内核
- SQL2012之FileTable与C#的联合应用
- 【Android】ScrollView+GridView 显示问题
- 多个 (li) 标签如何获取获取选中的里面的某个特定值??
- Vue入门总结
- pytorch可视化工具visdom
- [转载] Fiddler为所欲为第三篇 封包逆向必备知识[三]
- Go Example--缓存通道
- shopify网站转化率优化之结账页checkout优化
- Ioc:The basic pattern for integrating Autofac into your application
- 14 MySQL--事务&;函数与流程控制
- 程序集(Assembly)和模块(Managed Module)
- MySQL 语句分析
- 架构师养成记--35.redis集群搭建