题目链接：http://poj.org/problem?id=3254
题目大意：Farmer John 放牧cow，有些草地上的草是不能吃的，用0表示，然后规定两头牛不能相邻放牧。问你有多少种放牧方法。
Sample Input
2 3
1 1 1
0 1 0
Sample Output
9
分析：对于这种二维地图型，一般设状态dp[i][j]表示第 i 行第 j 状态达到要求的总数
输入地图，用map[i]表示第 i 行中的状态。为了是sta[k]表示可行状态更加方便，map[i]中用0表示可放牧，1表示不可放牧，这样如果（sta[k]&map[i]==0）则说明满足放牧要求。
动态规划：初始化：令dp[0][j]中可以在第一行放牧的状态j，dp[0][j]=1;
转移方程：dp[i][j] = dp[i][j] + dp[i-1][k],k为所有满足条件的状态
代码如下：
# include<stdio.h>
# include<string.h>
const int MAXN = <<;
const int MOD = ;
int sta[MAXN],num;
int dp[][MAXN]; //dp[i][j]表示第i行在集合j中满足条件的方案数
int map[]; //表示输入中每一行的状态
int n,m;
void init(){
num =;
int sum = <<m;
for(int i=; i<sum;i++) //从1到sum里边有满足该状态中放牛的位置不相邻的方案有num个
if(i&(i<<))
continue;
else
sta[num++] = i;
} void DP(){
int i,j,k;
for(i=; i<num; i++)
if(!(sta[i]&map[])) //寻找第一层满足条件的方案，令它为1
dp[][i] = ;
for(i=; i<n; i++)
for(j=; j<num; j++) //第i行是状态j
if(sta[j]&map[i]) //去掉与草场矛盾
continue;
else
for(k=; k<num; k++){ //第i-1行是状态k
if(map[i-]&sta[k]) //去掉与草场矛盾的
continue;
if(sta[k]&sta[j]) //去掉与上一行状态矛盾的
continue;
dp[i][j] = (dp[i][j] + dp[i-][k]) % MOD;
}
int ans = ;
for(i=; i<num; i++)
ans = (ans+dp[n-][i])%MOD;
printf("%d\n",ans);
}
int main(){
int i,j,temp;
while(scanf("%d%d",&n,&m)!=EOF){
memset(map,,sizeof(map));
for(i=; i<n; i++)
for(j=; j<m; j++){
scanf("%d",&temp);
if(temp==) //将每行状态二进制表示，1代表题目中的0，代表1
map[i] += <<(m-j-);
}
init();
DP();
}
return ;
}
也可以使用滚动数组：
# include<stdio.h>
# include<string.h>
const int MAXN = <<;
const int MOD = ;
int sta[MAXN],num;
int dp[][MAXN]; //dp[i][j]表示第i行在集合j中满足条件的方案数
int map[]; //表示输入中每一行的状态
int n,m;
void init(){
num =;
int sum = <<m;
for(int i=; i<sum;i++) //从1到sum里边有满足该状态中放牛的位置不相邻的方案有num个
if(i&(i<<))
continue;
else
sta[num++] = i;
} void DP(){
int i,j,k;
memset(dp,,sizeof(dp));
for(i=; i<num; i++)
if(!(sta[i]&map[])) //寻找第一层满足条件的方案，令它为1
dp[][i] = ;
for(i=; i<n; i++){
for(j=; j<num; j++) { //第i行是状态j
dp[i%][j] = ; //用来初始化，在滚动数组里边很重要
if(sta[j]&map[i]) //去掉与草场矛盾
continue;
else
for(k=; k<num; k++){ //第i-1行是状态k
if(map[i-]&sta[k]) //去掉与草场矛盾的
continue;
if(sta[k]&sta[j]) //去掉与上一行状态矛盾的
continue;
dp[i%][j] = (dp[i%][j] + dp[(i+)%][k]) % MOD;
}
}
}
int ans = ;
int temp = (n+)%;
for(i=; i<num; i++)
ans = (ans+dp[temp][i])%MOD;
printf("%d\n",ans);
}
int main(){
int i,j,temp;
while(scanf("%d%d",&n,&m)!=EOF){
memset(map,,sizeof(map));
for(i=; i<n; i++)
for(j=; j<m; j++){
scanf("%d",&temp);
if(temp==) //将每行状态二进制表示，1代表题目中的0，代表1
map[i] += <<(m-j-);
}
init();
DP();
}
return ;
}