题目传送门

sol：状压和动规，把每一行的m个01压缩成一个int

状压dp

#include "bits/stdc++.h"

using namespace std;

const int MAXN = ;

const int MOD = 1e8;

int n, m;

bool mp[MAXN][MAXN];

vector<int> num[MAXN], dp[MAXN];

void dfs(int i, int j, int k) {

    if (j > m) {

        num[i].push_back(k);

        dp[i].push_back();

        return;

    }

    dfs(i, j + , k  << );

    if ((k & ) ==  && mp[i][j + ] == ) dfs(i, j + , k <<  | );

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= m; j++) scanf("%d", &mp[i][j]);

        dfs(i, , );

    }

    for (int j = ; j < dp[].size(); j++) dp[][j] = ;

    for (int i = ; i <= n; i++) {

        for (int j = ; j < dp[i].size(); j++) {

            for (int k = ; k < dp[i - ].size(); k++) {

                if ((num[i][j] & num[i - ][k]) == )

                {

                    dp[i][j] = (dp[i][j] + dp[i - ][k]) % MOD;

                }

            }

        }

    }

    int ans = ;

    for (int j = ; j < dp[n].size(); j++) ans = (ans + dp[n][j]) % MOD;

    printf("%d\n", ans);

    return ;

}

巴特西

牛客-Corn Fields

题目传送门

最新文章

热门文章