JZOJ 1266. 玉米田

traveller-ly 2018-07-19 原文

JZOJ 1266. 玉米田

Description

　　农民 John 购买了一处肥沃的矩形牧场，分成M*N(1 <= M <= 12; 1 <= N <= 12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。精明的 FJ 知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。　　作为一个思想开明的人，农民 John 希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子都不选择的种植方案！请帮助农民 John 确定种植方案总数。

Input

　　Line 1: 两个用空格分隔的整数 M 和 N
　　Lines 2..M+1: 第 i+1 行描述牧场第i行每个格子的情况， N 个用空格分隔的整数，表示这个格子是否可以种植(1 表示肥沃的、适合种植，0 表示贫瘠的、不可种植)

Output

　　Line 1: 一个整数: FJ 可选择的方案总数除以 100,000,000 的余数。

Sample Input

2 3
1 1 1
0 1 0

Sample Output

做法：直接将状态压缩，然后dp统计就好了，转移方程与预处理看代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #define LL long long
 6 #define mo 100000000
 7 using namespace std;
 8 long long f[13][4100], e[13][4100], ans;
 9 int n, m, a[13][13];
10 int pre[20];
11 
12 void dfs(int h, int dep, int s, int choose)
13 {
14     if (dep > m)
15     {
16         e[h][++e[h][0]]    = s;
17         return;
18     }
19     if (a[h][dep] && !choose)    dfs(h, dep + 1, s + pre[dep - 1], 1);
20     dfs(h, dep + 1, s, 0);
21 }
22 
23 void pre_work()
24 {
25     pre[0] = 1;
26     for (int i = 1; i <= 18; i++)
27         pre[i] = pre[i - 1] * 2;
28     for (int i = 1; i <= n; i++)
29         dfs(i, 1, 0, 0);
30 }
31 
32 void dp()
33 {
34     for (int i = 1; i <= e[1][0]; i++)
35         f[1][e[1][i]] = 1;
36     for (int i = 2; i <= n; i++)
37     {
38         for (int j = 1; j <= e[i][0]; j++)
39             for (int k = 1; k <= e[i - 1][0]; k++)
40                 if ((e[i][j] & e[i - 1][k]) == 0)    
41                     f[i][e[i][j]] += f[i - 1][e[i - 1][k]];
42     }
43     ans = 0;
44     for (int i = 1; i <= e[n][0]; i++)
45         ans += f[n][e[n][i]], ans %= mo;    
46 }
47 
48 int main()
49 {
50     freopen("cowfood.in", "r", stdin);
51     freopen("cowfood.out", "w", stdout);
52     scanf("%d%d", &n, &m);
53     for (int i = 1; i <= n; i++)
54     {
55         for (int j = 1; j <= m; j++)
56             scanf("%d", &a[i][j]);
57     }
58     pre_work();
59     dp();
60     printf("%lld", ans);
61 }