【每日一题】德玛西亚万岁

德玛西亚万岁

https://ac.nowcoder.com/acm/problem/15034

题目

题目描述：

    德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。

    这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。

    有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。

    结果比尔吉沃特领土太小，只有长为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数组的含义：
1. 因为我们只在意哪个位置要选，和选多少次。所以我们就定义为dp[行][列] = 情况数量。
然后就是递推：
1. 递推的时候，这一行每个位置上的可能性是上一行每个位置上的可能性之和。
2. 但是要注意几个点：（下面用j表示这一行的二进制表示，比如第一行的山丘安排情况是101，我们就用十进制存储为5）（k表示j上面一行的）
  1. <1>第一是左右相邻位置上不可以有都进行放置：我们用j & (j >> 1)来判断。
  2. <2>第二是有没有位置已经被安排到不能选的了：我们用(mp[i] & j) != j来判断。
  3. <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;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏