poj3254--Fields+狀態壓縮dp

poj3254--Fields+狀態壓縮dp

第一道狀態壓縮dp :)

考慮每一行的情況，如果我們令0表示不可以放牧1表示放牧，那麼這一行所有可行的情況都可以窮舉出來並對應到一個十進制的數；這就是狀態壓縮。再由題目可以知道每一行的狀態可不可以出現只和它前面的那一行有關，所以我們可以定義 dp[i][j]表示第i行處於第j種狀態的時候有多少種放牧的方法；

dp[i][j]=dp[i-1][j1]+dp[i-1][j2]+。。。。+dp[i-1][jn],其中j要和jn能同時出現。

由這個方程我們就可以寫程序了，我們可以選擇用一個數組來表示狀態然後進行相應的判斷，但是我們可以通過位運算更方便的實現這些判斷。

首先我們不需要把窮舉每個狀態，我們可以通過題目限制條件（兩個1不能相鄰）先篩選出所有合法的狀態,這個操作用x&(x<<1)進行判斷，如果為0則表示無相鄰否則相反；然後我們還要判斷這些合法狀態是否和是否和初始狀態沖突，這時我們需要將初始狀態01取反，0變成1,1變成0(這樣只需要判斷如果與原狀態1位置上對應的狀態是不是0，可以通過&實現)，這樣我們只需要將某個狀態與其&，如果為1則表示不合法，為0則合法。最後我們需要判斷對應兩個數的二進制表示的相同位是否同時為1，這個也可以通過&實現。

這些操作都用位運算實現後，我們就可以方便的寫出代碼了。

代碼如下

#include
#include
#include
using namespace std;

#define mod 1000000000
int total[1000];
int dp[15][1000];
int top;
int cur[15];
int n,m;

int ok(int i,int j)
{
    if(i&j)
       return 0;
    return 1;
}

void Allstate()
{
    top=1;
    int j=1<