题目

题目描述:

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

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

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

    结果比尔吉沃特领土太小,只有长为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)算法分析

  1. 这道题数据范围很小,加上只有放和不放两种情况。就是赤裸裸的暗示我们暴力,用二进制枚举,状压dp
  2. 既然都说了是dp:动态规划重要的就是递推和dp数组的含义
  3. 首先是dp数组的含义
    1. 因为我们只在意哪个位置要选,和选多少次。所以我们就定义为dp[行][列] = 情况数量
  4. 然后就是递推
    1. 递推的时候,这一行每个位置上的可能性是上一行每个位置上的可能性之和
    2. 但是要注意几个点:(下面用j表示这一行的二进制表示,比如第一行的山丘安排情况是101,我们就用十进制存储为5)(k表示j上面一行的)
      1. <1>第一是左右相邻位置上不可以有都进行放置:我们用j & (j >> 1)来判断。
      2. <2>第二是有没有位置已经被安排到不能选的了:我们用(mp[i] & j) != j来判断。
      3. <3>第三是判断上下相邻的情况:我们用j & k来判断。

4)算法操作

  1. 首先就是我们是矩阵怎么存储的,可能上面无法理解的很清楚,我们是一行看成了一组二进制,用十进制存储的
    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
        }
    
  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;
            }
        }
  3. 上面简单解释一下就是:先暴力枚举行,再二进制枚举列,再二进制枚举上一列

5)打代码

  1. 首先二进制保存矩阵。
  2. 然后就dp呗。
  3. 下面全代码~


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;
}
//函数区