状态压缩dp，数据弱，本程序时间效率O(12 * (2^24))
View Code #include#include #include #include using namespace std;#define maxn 13#define mod 100000000int row, column;int filter[maxn];int f[maxn][1 << maxn];void input(){ scanf("%d%d", &row, &column); for (int i = 1; i <= row; i++) { filter[i] = 0; for (int j = 0; j < column; j++) { int a; scanf("%d", &a); filter[i] = (filter[i] << 1) + a; } }}bool ok(int a, int b){ if ((a & filter[b]) != a) return false; int x = 3; for (int i = 0; i < column - 1; i++) { if ((a & x) == x) return false; x = x << 1; } return true;}void work(){ memset(f, 0, sizeof(f)); int n = 1 << column; f[0][0] = 1; for (int i = 1; i <= row; i++) { for (int j = 0; j < n; j++) { if (!ok(j, i)) continue; for (int k = 0; k < n; k++) if ((k & j) == 0) f[i][j] = (f[i][j] + f[i - 1][k]) % mod; } } int ans = 0; for (int i = 0; i < n; i++) ans = (ans + f[row][i]) % mod; printf("%d\n", ans);}int main(){ //freopen("t.txt", "r", stdin); input(); work(); return 0;}