程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj3254

poj3254

編輯:關於C++

第一道狀態壓縮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<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved