题目
题目描述:
德玛西亚是一个实力雄厚、奉公守法的国家,有着功勋卓著的光荣军史。
这里非常重视正义、荣耀、职责的意识形态,这里的人民为此感到强烈自豪。
有一天他们想去制裁邪恶的比尔吉沃特,于是派遣了自己最优秀的战士。
结果比尔吉沃特领土太小,只有长为n宽为m共计n*m块土地,其中有些土
地标记为0表示为高山峻岭或者深海湖泊,英雄们无法在其中站立,只有标
记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点,他
们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西
亚英雄的方法?
输入描述:
输入包含多组测试数据;
每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 ),之间用空格隔开;
接下来的n行,每行m个数,表示n*m的比尔吉沃特领土。
输出描述:
输出一个整数n代表安排应用的方法。(答案取膜100000000)
解析
1)知识点
这道题就是二进制枚举+状压dp。
2)看题目
看题目的意思就是,n * m的矩阵,有多少种不相邻的放棋子的情况(有的位置不能放棋子)。
3)算法分析
- 这道题数据范围很小,加上只有放和不放两种情况。就是赤裸裸的暗示我们暴力,用二进制枚举,状压dp。
- 既然都说了是dp:动态规划重要的就是递推和dp数组的含义。
- 首先是dp数组的含义:
- 因为我们只在意哪个位置要选,和选多少次。所以我们就定义为dp[行][列] = 情况数量。
- 然后就是递推:
- 递推的时候,这一行每个位置上的可能性是上一行每个位置上的可能性之和。
- 但是要注意几个点:(下面用j表示这一行的二进制表示,比如第一行的山丘安排情况是101,我们就用十进制存储为5)(k表示j上面一行的)
- <1>第一是左右相邻位置上不可以有都进行放置:我们用j & (j >> 1)来判断。
- <2>第二是有没有位置已经被安排到不能选的了:我们用(mp[i] & j) != j来判断。
- <3>第三是判断上下相邻的情况:我们用j & k来判断。
4)算法操作
- 首先就是我们是矩阵怎么存储的,可能上面无法理解的很清楚,我们是把一行看成了一组二进制,用十进制存储的:
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int x; cin >> x; mp[i] = (mp[i] << 1) + x;//下一个数进来就让原先的值*2 }
- 然后就是暴力求解了,包括多种判断情况,看一下代码吧:
memset(dp, 0, sizeof dp); dp[0][0] = 1; int len = 1 << m; for (int i = 1; i <= n; i++)//枚举行 for (int j = 0; j < len; j++) {//枚举列 if (j & (j >> 1)) continue;//判断是否有相邻 if ((mp[i] & j) != j) continue;//判断是否有已选位为1 for (int k = 0; k < len; k++) {//判断上一行的情况 if (k & j) continue;//上下相邻 dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD; } }
- 上面简单解释一下就是:先暴力枚举行,再二进制枚举列,再二进制枚举上一列。
5)打代码
- 首先二进制保存矩阵。
- 然后就dp呗。
- 下面全代码~
AC代码
#include <iostream> #include <cstring> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MOD = 1e8; int n, m; ll mp[17], dp[17][1 << 17]; //全局变量区 //函数预定义区 int main() { IOS; while (cin >> n >> m) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int x; cin >> x; mp[i] = (mp[i] << 1) + x; } memset(dp, 0, sizeof dp); dp[0][0] = 1; int len = 1 << m; for (int i = 1; i <= n; i++)//枚举行 for (int j = 0; j < len; j++) {//枚举列 if (j & (j >> 1)) continue;//判断是否有相邻 if ((mp[i] & j) != j) continue;//判断是否有已选位为1 for (int k = 0; k < len; k++) {//判断上一行的情况 if (k & j) continue;//上下相邻 dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD; } } ll ans = 0; for (int i = 0; i < len; i++) ans = (ans + dp[n][i]) % MOD; cout << ans << endl; } return 0; } //函数区