題意:

n*m網格1能放0不能放 放的格子不能相鄰 求一共多少種可放的方案。

分析：

dp[i][j]第i行可行狀態j的的最大方案數，枚舉當前行和前一行的所有狀態轉移就行了（不放牛也算一種情況）

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod =  100000000;
int dp[15][5000],n,m,a[15][15];
int judge(int i,int x){int t=x;int m1=m;while(m1--){if((x&1)&&a[i][m1]==0)return 0;x>>=1;}if(((t<<1)&t)==0&&((t>>1)&t)==0){return 1;}return 0;
}
void solve(){memset(dp,0,sizeof(dp));for(int i=0;i<(1<<m);++i){if(judge(0,i))dp[0][i]=1;}for(int i=1;i<n;++i){for(int j=0;j<(1<<m);++j){for(int k=0;k<(1<<m);++k)if(judge(i,j)&&judge(i-1,k)&&(j&k)==0)dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;}}int total=0;for(int i=0;i<(1<<m);++i)total=(total+dp[n-1][i])%mod;printf("%d\n",total);
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++)for(int j=0;j<m;++j)scanf("%d",&a[i][j]);solve();}
return 0;
}

　　

轉載于:https://www.cnblogs.com/zsf123/p/4673687.html

總結

以上是生活随笔為你收集整理的Corn Fields(POJ 3254状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。