1266. 玉米田(cowfood.pas/c/cpp)
(File IO): input:cowfood.in output:cowfood.out
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Goto ProblemSet做法:直接将状态压缩,然后dp统计就好了,转移方程与预处理看代码
View Code
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 }
代码如下: