题解-铺瓷砖

Description

今天小信装修新家，给家里买了一种 1×2的长方形（如图1）新瓷砖。小信是个懂得审美的人，毕竟人生除了金钱，还有诗和远方。这个时候小信就在想，这种长方形的瓷砖铺到一个 n×m 的地面上有多少种方案（如图2：是 4×4 地面的一种方案）?

Input

输入两个整数 n，m，(1≤MIN(n,m)≤10, 1≤MAX(n,m)≤100)。

Outputa

输出方案总数（最后结果模 10^9 + 7）。
Sample Input 1
2 2
Sample Output 1
2

解析讲解

这道题的数据与题干很明显就会联想到状态压缩（或状压DP）。

状压DP

状压DP实际就是暴力枚举，时间空间消耗少，将状态压缩存进int类型中，比如可以处理一些麻烦的题，细节麻烦的问题中。用例子来讲，01背包i,j就是时态的个更新，主要的还是二进制的问题，‘0’表示不选，‘1’反之。连成串后再转成十进制数。

运算符

在之前写过一篇运算符的概括，单目运算符，双目运算符,三目运算符都有，大家可一去看一下：https://blog.csdn.net/ebirth/article/details/96591827
对于状压DP，这还是把运算符都列举出来：

&       与运算   
|       或运算   
^       异或运算   
！      非运算(求补)   
>>      右移运算   
<<      左移运算   

• 与运算（&）
  双目运算。二个位都置位(等于1)时，结果等于1，其它的结果都等于0。

    1       &       1       ==       1   1       &       0       ==       0   0       &       1       ==       0   0       &       0       ==       0

• 或运算( | )
  双目运算。二个位只要有一个位置位，结果就等于1。二个位都为0时，结果为0。

    1       |       1       ==       1   1       |       0       ==       1   0       |       1       ==       1   0       |       0       ==       0

• 异或运算(^)
  双目运算。二个位不相等时，结果为1，否则为0。

    1       ^       1       ==       0   1       ^       0       ==       1   0       ^       1       ==       1   0       ^       0       ==       0

• 非运算(！)
  单目运算。位值取反，置0为1，或置1为0。非运算的用途是将指定位清0，其余位置1。非运算与数值大小无关。
• &，&&，|，||
  &&相当一个开关语句，就是说如果&&前面值为false那么他就不继续执行后面的表达式；而&不管前面的值为什么，总是执行其后面的语句。&& 和 || 是boolean的逻辑运算， 返回为bool值 。&是位运算符,它会将两边的运算都计算出来,再进行与运算; &是用来处理0101这样的2进制字符的位运算的。&&是布尔逻辑运算符（短路运算）,只要有一边的运算结果为false,它都会马上返回false；&&是处理true和false这样的boolean运算。同样的道理，|| 也是布尔逻辑运算符，只要有一边的运算结果是true，它会马上返回true。
• 取反运算（~）
  取反，将二进制为取反，1变成0，0变成1。

检查第i位是否有1：

if(1<<(i-1)&x)...

检查第i位是否有0：

if(1<<(i-1)&x==0)...

统计x中有多少个 1：

while(x){cnt+=x&1;x>>=1;}

检查中是否有相邻的 1：

if(x&(x<<1))...

计算x最低位1代表的值：

intlowbit(intx){returnx&(-x);//用到负数补码的性质，可以不深究}

把第i位取反:

x^= (1<<(i-1))

在这里我就不多说了 ，我给一个比较简单的列题（01背包），用状态DP

//01背包状压暴力枚举
#include <bits/stdc++.h>
using namespace std;
int W[35], C[35];
int n, m;
int count_value(int x)//x存状态 {int w = 0;int c = 0;for(int i = 1; x; x>>=1,i++){if(x&1){w += W[i];c += C[i];if(w > m) return 0;//重量超限了，无效 }}return c;
}
int main(){cin >> m >> n;for(int i = 1; i <= n; i++)cin >> W[i] >> C[i];int ans = 0;for(int i = 1; i < 1<<n; i++)//枚举所有选取方案（指数级） ans = max(ans, count_value(i));		cout << ans << endl;return 0;
}

题目分析

题目中给了我们两组方案：横铺与竖铺。
总体一大串废话总结一句：给出 n×m的矩形方块，可以往上面铺1×2的砖块，问铺满这个方块的方案有多少种。

之前看到过有人用DFS的做法，但很不幸，直接超时。
接下来，给大家看有图：

我们按照题目中的说法去做。
不如用另一种方法:我们每行枚举，二进制数中1，0分别代表，看看横排与竖排的边是0还是1。我们发现[i-1,j]如果为1的话，且[i,j]也是1，那么次此时可以判断出是横铺。

只要保证[i-1,j]上一行不是0，那么下一行就不会受影响，此时便能判断。

代码部分

#include<bits/stdc++.h> 
using namespace std;
int n,m;
int dp[20000][1<<11];
cosnt int mod=1000000007;
bool check(const int &x){int k=0;while(k<m){if(x>>k&1)k++;else if(k+1<m&&~x>>k+1&1)k+=2;else return false;}return true;
}
int main(){cin>>n>>m;if(n<m)swap(n,m);for(int i=0;i<1<<m;i++){if(check(i))dp[0][i]=1;}for(int i=1;i<n;i++){for(int j=0;j<1<<m;j++){for(int k=0;k<1<<m;k++){if(!(j&k)&&check(j|k)){dp[i][k]=(dp[i][k]+dp[i-1][j])%mod;}} }}cout<<dp[n-1][0];return 0;
}