題意:
給一塊m行n列的土地,有一些格可以種樹,另外一些不可以,樹不能相鄰,問一共有多少種種法。
分析:
從後往前種,子問題向父問題擴展,當種到某一格時只有他和他後面的n-1個格子的情況對它有影響,故對這n個格子進行編碼為狀態S,表示種完(多米諾骨牌那題是放置前,注意區別,都可行)這n個格子的狀態。父問題由稍小子問題逐步解決,正是動態規劃的思想。
代碼:
//poj 3254 //sep9 #includeusing namespace std; const int maxN=14; const int mod=100000000; int land[maxN][maxN]; int dp[2][1< =0;--i) for(j=n-1;j>=0;--j){ for(used=0;used<1< >j&1) nxt[used]=0; else{ nxt[used]=cur[used]; nxt[used]+=cur[used|(1< >j&1)&&(used>>(j+1)&1)){ res=0; }else if(!(used>>j&1)&&(used>>(j+1)&1)){ res=cur[used]; res+=cur[used|(1< >j&1)&&!(used>>(j+1)&1)){ res=cur[used&(~(1< >j&1)&&!(used>>(j+1)&1)){ res=cur[used]; res+=cur[used|(1<