poj3254 Corn Fields 状压DP入门
Corn Fields
| Time Limit:?2000MS | ? | Memory Limit:?65536K |
| Total Submissions:?19368 | ? | Accepted:?10169 |
Description
Farmer John has purchased a lush new rectangular pasture composed of?M?by?N?(1 ≤?M?≤ 12; 1 ≤?N?≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
Input
Line 1: Two space-separated integers:?M?and?N?
Lines 2..M+1: Line?i+1 describes row?i?of the pasture with?N?space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)
Output
Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.
Sample Input
2 3 1 1 1 0 1 0Sample Output
9Hint
Number the squares as follows:
1 2 34 ?
There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
Source
USACO 2006 November Gold
題意：
農夫有一塊地，被劃分為m行n列大小相等的格子，農夫要在地里種草。但是有些地土壤不適合種草(0)，有些可以種草(1)。
并且不能再相鄰的兩塊地種草。問農夫最多有多少種方法種草。
任何格子都不放也是一種選擇，不要忘記考慮！
分析：
以樣例數據第一行為例，三個格子都可以放牧，即每個格子都可以選擇放，或不放。再考慮附加條件“相鄰格子不可同時放牧”，那么我們可以列出單看第一行時的所有可行狀態如下（1代表放牧，0代表不放牧）
| 編號 | 狀態 |
| 1 | 0 0 0? |
| 2 | 0 0 1 |
| 3 | 0 1 0 |
| 4 | 1 0 0 |
| 5 | 1 0 1 |
由此，可將表中的狀態看作二進制表示，那么，只需將每種狀態轉化為相應的十進制數，即可只用一個數字，
就能表示某一種狀態，如下表：
| 編號 | 二進制 | 十進制 |
| 1 | 0 0 0 | 0 |
| 2 | 0 0 1 | 1 |
| 3 | 0 1 0 | 2 |
| 4 | 1 0 0 | 4 |
| 5 | 1 0 1 | 5 |
這種用一個數來表示一組數，以降低表示狀態所需的維數的解題手段，就叫做狀態壓縮。
至此我們看到，在只考慮第一行的時候，有5種可行的放牧方案，但這只是我們要做的第一步。接下來要將第二行納入考慮：
首先思考：納入第二行后，會對當前問題造成什么樣的影響？
答案還是那句話：“相鄰格子不可同時放牧”！
也就是說，不止左右相鄰不可以，上下之間也不能存在相鄰的情況。
首先觀察第二行，只有中間的格子可以放牧，那么我們的狀態表格就可以相對簡單些了～如下：
| 編號 | 二進制 | 十進制 |
| 1 | 0 0 0 | 0 |
| 2 | 0 1 0 | 2 |
只有兩種可行狀態，那么我們不妨一個一個來考察：
1、當第二行的狀態為編號1時，第二行的三個格子都沒有放牧，那么就不會與第一行的任何情況有沖突，
第一行的5種方案都可行，即：第二行選用編號1的狀態時，結合第一行，可得到5種可行的放牧方案；
2、當第二行的狀態為編號2時，第二行中間的格子已經放牧了，那么第一行中間的格子就不可以放牧。
看表2，發現其中第3種狀態與當前第二行沖突，那么第一行只有4種方案是可行的，
即：第二行選用編號2的狀態時，結合第一行，可得到4種可行的放牧方案；
那么，在樣例數據給出的情況下，我們的最終答案即為5+4=9；
?
通過對樣例數據的分析即可以發現不同狀態之間的關系：
以dp[i][state(j)]來表示對于前i行，第i行采用第j種狀態時可以得到的可行方案總數！
例如：回頭看樣例數據，dp[2][1]即代表第二行使用第2中狀態（0 1 0）時可得的方案數，即為4；
那么，可得出狀態轉移方程為：
dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)]
(kn即為上一行可行狀態的編號，上一行共有n種可行狀態）
最終ans=dp[m][state(k1)]+dp[m][state(k2)]+......+dp[m][state(kn)];?(kn即為最后一行（第m行）可行狀態的編號）
#include <cstdio> #include <cstring> using namespace std; #define mod 100000000 int M,N,top = 0; //top表示每行最多的狀態數int state[600],num[110]; //state存放每行所有的可行狀態（即沒有相鄰的狀態int dp[20][600]; //dp[i][j]:對于前i行數據，每行有前j種可能狀態時的解 int cur[20]; //cur[i]表示的是第i行整行的情況inline bool ok(int x){ //判斷狀態x是否可行if(x&x<<1) return false;//若存在相鄰兩個格子都為1，則該狀態不可行return true; } void init(){ //遍歷所有可能的狀態top = 0;int total = 1 << N; //遍歷狀態的上界for(int i = 0; i < total; ++i){if(ok(i))state[++top] = i;} } inline bool fit(int x,int k){ //判斷狀態x 與第k行的實際狀態的逆是否有‘重合’if(x&cur[k])return false; //若有重合，（即x不符合要求）return true; //若沒有，則可行 }int main(){while(scanf("%d%d",&M,&N)!= EOF){init();memset(dp,0,sizeof(dp));for(int i = 1; i <= M; ++i){cur[i] = 0;int num;//輸入時就要按位來存儲，cur[i]表示的是第i行整行的情況，每次改變該數字的二進制表示的一位for(int j = 1; j <= N; ++j){scanf("%d",&num); //表示第i行第j列的情況（0或1）if(num == 0) //若該格為0cur[i] +=(1<<(N-j));//則將該位置為1（注意要以相反方式存儲，即1表示不可放牧}}for(int i = 1;i <= top;i++){if(fit(state[i],1)){ //判斷所有可能狀態與第一行的實際狀態的逆是否有重合dp[1][i] = 1; //若第1行的狀態與第i種可行狀態吻合，則dp[1][i]記為1}}/*狀態轉移過程中，dp[i][k] =Sigma dp[i-1][j] （j為符合條件的所有狀態）*/for(int i = 2; i <= M; ++i){ //i索引第2行到第M行for(int k = 1; k <= top; ++k){//該循環針對所有可能的狀態，找出一組與第i行相符的state[k]if(!fit(state[k],i))continue; //判斷是否符合第i行實際情況for(int j = 1; j <= top ;++j){//找到state[k]后，再找一組與第i-1行符合，且與第i行（state[])不沖突的狀態state[j]if(!fit(state[j],i-1))continue; //判斷是否符合第i-1行實際情況if(state[k]&state[j])continue; //判斷是否與第i行沖突dp[i][k] = (dp[i][k] +dp[i-1][j])%mod; //若以上皆可通過，則將'j'累加到‘k'上}}}int ans = 0;//累加最后一行所有可能狀態的值，即得最終結果for(int i = 1; i <= top; ++i){ans = (ans + dp[M][i])%mod;}printf("%d\n",ans);} }?
總結
以上是生活随笔為你收集整理的poj3254 Corn Fields 状压DP入门的全部內容，希望文章能夠幫你解決所遇到的問題。
