Corn Fields POJ - 3254 （状压dp）
题目链接：
Corn Fields
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：给你一个n*m的矩阵，矩阵的元素只包括0和1，0代表当前的位置不能放置人，1代表当前的位置可以放人，当你决定放人的时候，这个人的四个方向都不能放人，然后问你一共有多少种放置方式。
具体思路：二进制枚举，每一次判断和上下左右位置是否冲突就好了。
AC代码：
1 #include<iostream> 2 #include<stdio.h> 3 #include<cmath> 4 #include<string> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 # define ll long long 9 # define inf 0x3f3f3f3f 10 const int maxn = 5e3+100; 11 const int mod = 1e9; 12 int dp[20][maxn]; 13 int a[20][20]; 14 int n,m; 15 bool check(int t1,int t2) 16 { 17 if((((t2<<1)&t2)==0)&&(((t2>>1)&t2)==0)) 18 { 19 for(int j=0; j<m; j++){ 20 if(((t2&(1<<j))&&a[t1][j])||(!(t2&(1<<j)))) 21 continue; 22 else 23 return false; 24 } 25 return true; 26 } 27 else 28 return false; 29 } 30 int main() 31 { 32 scanf("%d %d",&n,&m); 33 for(int i=0; i<n; i++) 34 { 35 for(int j=0; j<m; j++) 36 { 37 scanf("%d",&a[i][j]); 38 } 39 } 40 int maxstate=(1<<m)-1; 41 for(int i=0; i<n; i++) 42 { 43 if(i==0) 44 { 45 for(int j=0; j<=maxstate; j++) 46 { 47 if(check(i,j)) 48 dp[i][j]++; 49 } 50 } 51 else 52 { 53 for(int j=0; j<=maxstate; j++) 54 { 55 for(int k=0; k<=maxstate; k++) 56 { 57 if(check(i,k)&&((j&k)==0)) 58 { 59 dp[i][k]+=dp[i-1][j]; 60 } 61 } 62 } 63 } 64 } 65 // for(int i=0;i<=maxstate;i++){ 66 // cout<<i<<" "<<dp[0][i]<<endl; 67 // } 68 ll sum=0; 69 for(int i=0; i<=maxstate; i++) 70 { 71 sum=(sum+dp[n-1][i])%mod; 72 } 73 printf("%lld\n",sum); 74 return 0; 75 }
更多精彩
