题意：一个n*m的矩阵，每个格子是0或者1，1表示土壤肥沃可以种植草地，0则不可以。在种草地的格子可以放牛，但边相邻的两个格子不允许同时放牛，问总共有多少种放牛的方法？（不放牛也算一种情况）
思路：就是POJ 1185 炮兵阵地的弱化版，，炮兵那题相当于间隔两行，这里是间隔一行，减少一维坐标就可
//192 KB32 msC++1221 B#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int mod = 100000000;int stnum[15];int state[15][500];int dp[15][500];int n,m;int main(){while(~scanf("%d%d",&n,&m)){memset(dp,0,sizeof(dp));memset(stnum,0,sizeof(stnum));for(int i=1;i<=n;i++){int g=0;for(int j=0;j<m;j++){int t;scanf("%d",&t);g += (t==1)? (1<<j):0;}for(int s=0;s<1<<m;s++){if((s|g)!=g) continue;if((s>>1)&s) continue;stnum[i]++;state[i][stnum[i]]=s;}}for(int i=1;i<=stnum[1];i++)dp[1][i]=1;for(int i=2;i<=n;i++)for(int j=1;j<=stnum[i];j++)for(int k=1;k<=stnum[i-1];k++){if(state[i][j]&state[i-1][k]) continue;dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;}int ans=0;for(int i=1;i<=stnum[n];i++)ans=(ans+dp[n][i])%mod;printf("%d\n",ans);}return 0;}
代替你主持夕阳的葬礼。
