POJ-3254 Corn Fields 状压dp入门

本文主要是介绍POJ-3254 Corn Fields 状压dp入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：n*m个方格，在数字为1的方格中可以种草，相邻的方格不能同时种，问一共有多少种种法。

dp[i][j]表示第i行的状态为j时有多少种种法，j为状态的2进制数，1表示种，0表示不种。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[13][5000];
int d[13];
int pw[20];
const int MOD = 100000000;
int main() {int n, m, i, j, a, k;pw[0] = 1;for(i = 1; i < 20; i++)pw[i] = pw[i-1]*2;while(~scanf("%d%d", &n, &m)) {memset(dp, 0, sizeof(dp));memset(d, 0, sizeof(d));for(i = 1; i <= n; i++) {for(j = 0; j < m; j++) {scanf("%d", &a);d[i] = (d[i]<<1)+a;}}dp[0][0] = 1;for(i = 1; i <= n; i++) {for(j = 0; j < pw[m]; j++) {if((j & (j << 1)) || (j & ~d[i])) continue;for(k = 0; k < pw[m]; k++) {if(!(k & j))dp[i][j] = (dp[i][j]+dp[i-1][k]) % MOD;}}}int ans = 0;for(i = 0; i < pw[m]; i++)ans = (ans + dp[n][i]) % MOD;printf("%d\n", ans);}return 0;
}

这篇关于POJ-3254 Corn Fields 状压dp入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---