POJ 3254 Corn Fields

题意:Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. some of the squares are infertile and can't be planted. (1 for fertile, 0 for infertile)cows dislike eating close to each other。Please help Farmer John determine the number of ways he can choose the squares to plant.
第一道状态压缩DP题,写的还挺顺利的。
第一具备位运算常识:
“&”按位与: 3: 0011, 5:0101; 那么3&5: 0011
&0101
0001
那么意味着只要有一位上都是1,那么&的结果就是>0 d的。
“|” 按位或只要俩个数字有一位是1 ,那么|的结果中相应位为13|5=0111;
“<<":
x< 3<<5是 00011 <<3等于 11000
【POJ 3254 Corn Fields】第二:
状态压缩DP,在我的理解中就是应用二进制数去标记所有状态。在根据二进制数本身特点去识别是不是有效状态。
根据代码解释:dp[i][j]表示第i 行状态j 的方案数
dp[i][j]=dp[i][j]+dp[i-1][j](j为所有合法状态)

#include #include #include using namespace std; const int MOD=100000000; int dp[13][1<<12]={0,0,0}; int n,m; int OK[1<<13]; int map[1<<13]; int main() { // freopen("in.txt","r",stdin); memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); int cnt=0; memset(OK,0,sizeof(OK)); for(int i=0; i< (1<



    推荐阅读