[USACO06NOV]Corn Fields G
题目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主 $\rm John$ 新买了一块长方形的新牧场,这块牧场被划分成 $M$ 行 $N$ 列 $(1 \le M \le 12; 1 \le N \le 12)$,每一格都是一块正方形的土地。 $\rm John$ 打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。
遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是 $\rm John$ 不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。
$\rm John$ 想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)
输入格式
第一行:两个整数 $M$ 和 $N$,用空格隔开。
第 $2$ 到第 $M+1$ 行:每行包含 $N$ 个用空格隔开的整数,描述了每块土地的状态。第 $i+1$ 行描述了第 $i$ 行的土地,所有整数均为 $0$ 或 $1$ ,是 $1$ 的话,表示这块土地足够肥沃,$0$ 则表示这块土地不适合种草。
输出格式
一个整数,即牧场分配总方案数除以 $100,000,000$ 的余数。
样例 #1
样例输入 #1
2 3
1 1 1
0 1 0
样例输出 #1
9
$\Huge\color{#8BA583}{对于此题,主要且中心的思路就是:}$
$\Huge\color{#D7000F}{状压dp}$
那么对于一些初学者的考虑
首先具体说明一下状压dp
状压dp
其本质就是位运算:
位运算:
程序中所有数在计算机内存中都是以二进制形式储存的 ,位运算说白了,就是直接对樟树在内存中的二进制 位进行操作
逻辑运算符
&位于运算,|位或运算,^为异或运算
位移运算符
<<位左移,>>位右移
位于运算
相同位的两个数字都为1,则为1;若有一个不为1,则为0
例如:
int型常量-4和7进行位与运算过程如下:
4&7
4=0000 0000 0000 0100
7=0000 00000 0000 0111
4&7=0000 0000 0000 0100
对于负数,按照其补码进行计算
下面是几个常见的详细介绍及运算说明:
and运算 &
and运算通常用于二进制的取位操作,例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数为偶数,最末位为1表示该数为奇数。
相同位的两个数字都为1,则为1;若有一个不为1,则为0。
(&;或者and)
or运算 |
or运算通常用于二进制特定位上的无条件赋值,例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0,对这个数or 1之后再减一就可以了,其实际意义就是把这个数强行变成最接近的偶数。
相同位只要一个为1即为1。
(|或者or)
xor运算 ^
异或的符号是^。按位异或运算, 对等长二进制模式按位或二进制数的每一位执行逻辑按位异或操作. 操作的结果是如果某位不同则该位为1, 否则该位为0.
xor运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即(a xor b) xor b = a。xor运算可以用于简单的加密,比如我想对我MM说1314520,但怕别人知道,于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500,我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值,得到1314520。
相同位不同则为1,相同则为0。
(^或者xor)
应用及变换操作
状压dp实质及实现
状压dp其实就是将状态压缩成2进制来保存 其特征就是看起来有点像搜索,每个格子的状态只有1或0 ,是另一类非常典型的动态规划
(补一句: 棋盘问题很多都用到了状压dp )
典例分析:
在一个n*n的棋盘中,每个格子中至多放置一个车,且要保证任何两个车都不能相互攻击,有多少中放法(车与车之间是没##有差别的)
那么对于此题,就是一道非常经典且基础的状压dp的题,只要我上面所述都理解了,那么解决此题应该问题不大~
下面来实现一下
CODE(C++)
#include<iostream>
#include<cstdio>
int f[1 << 22];
int main()
{
int n;
scanf("d", &n);
f[0] = 1;
for(int s=1;s <=(1 << n)-1;s++)
{
for(int i=1; i<=n; i++)
{
if((1<<i-1)&s)
{
int S = s&~(1 << (i-1))
f[s] += f[s];
}
}
}
printf("%d\n",f[(1 << n)] - 1);
}
如果上述感觉还好的话,那么就可以入手本题
此题经过分析,可以将玉米田看作一个棋盘,方法与例题差不多
实现一下:
CODE(C++)
#include <cstdio>
#include <iostream>
using namespace std;
const int mod=100000000;
int n,m,tot,v[20],ans;
int f[20][500],s[500];
int main()
{
scanf("%d%d",&n,&m);
int i,j,k,a;
for(i=0;i<1<<m;i++)
if((i&(i<<1))==0)
s[++tot]=i;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&a);
if(!a) v[i]+=1<<j-1;
}
}
f[0][1]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=tot;j++)
{
if(s[j]&v[i]) continue;
for(k=1;k<=tot;k++)
{
if(s[j]&s[k]) continue;
f[i][j]=(f[i][j]+f[i-1][k])%mod;
}
}
}
for(i=1;i<=tot;i++)
{
if(s[i]&v[n]) continue;
ans=(ans+f[n][i])%mod;
}
printf("%d",ans);
return 0;
}
是不是感觉还好的样子(指活着学废了qwq)