poj 3254 Corn Fields ，狀態壓縮DP

poj 3254 Corn Fields ，狀態壓縮DP

題目鏈接

題意:

一個矩陣裡有很多格子，每個格子有兩種狀態，可以放牧和不可以放牧，可以放牧用1表示，否則用0表示，在這塊牧場放牛，要求兩個相鄰的方格不能同時放牛，即牛與牛不能相鄰。問有多少種放牛方案(一頭牛都不放也是一種方案)

state[i] 表示對於一行，保證不相鄰的方案

狀態：dp[i][ state[j] ] 在狀態為state[j]時，到第i行符合條件的可以放牛的方案數

狀態轉移：dp[i][ state[j] ] =Sigma dp[i-1][state'] （state'為符合條件的所有狀態）

nclude
#include
#include
#include
using namespace std;

const int mod = 100000000;
int state[1<<13], cnt; //對於一行，保證不相鄰的方案
int dp[20][1<<13];
int cur[20]; // cur[i]的值得二進制形式0表示能放，1表示不能放。

int main()
{
    int n, m, i, j, k;
    scanf("%d%d", &n, &m);
    int M = 1<