[luoguP1879] [USACO06NOV]玉米田Corn Fields（DP）

传送门

说要统计方案，感觉就是个Σ

而矩阵中只有 01 ，可以用二进制表示

这样，预处理出每一个每一行所有可能的状态 s

然后初始化第一行所有状态的方案数为 1

f[i][j] =Σf[i 1][k] (k 和 j 不冲突，j 为第 i 行所有方案，k 为第 i 1 行所有方案)

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define mod 100000000 4 5 int n, m, ans; 6 int f[13][1 << 13], pos[13][1 << 13], s[13][1 << 13]; 7 8 inline int read() 9 16 17 inline void dfs(int k, int i, int num) 18 24 dfs(k, i + 1, num); 25 if((pos[k][i] ^ (pos[k][i 1] + 1)) || (i == 1)) 26 dfs(k, i + 1, num + (1 << pos[k][i] 1)); 27 else if((i ^ 1) && (pos[k][i] == pos[k][i 1] + 1)) 28 if(((num >> pos[k][i 1] 1) & 1) ^ 1) 29 dfs(k, i + 1, num + (1 << pos[k][i] 1)); 30 } 31 32 int main() 33 43 for(i = 1; i <= n; i++) dfs(i, 1, 0); 44 for(i = 1; i <= s[1][0]; i++) f[1][i] = 1; 45 for(i = 2; i <= n; i++) 46 for(j = 1; j <= s[i][0]; j++) 47 for(k = 1; k <= s[i 1][0]; k++) 48 if(!(s[i][j] & s[i 1][k])) 49 53 for(i = 1; i <= s[n][0]; i++) 54 58 printf("%d\n", ans); 59 return 0; 60 }
View Code

上一篇：[luoguP2659] 美丽的序列（单调栈）

下一篇：[luoguP2949] [USACO09OPEN]工作调度Work Scheduling（贪心 + 优先队列）

---

DP