http://poj.org/problem?id=3254
第一个状压题 思路挺好想 用二进制表示每行的状态 然后递推
用左移 右移来判断是不是01间隔出现 c大神教的 我的代码WA在这个地方了。。
改了点 就A了
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define mod 100000000
#define LL long long
int a[][];
LL dp[][],s[],num[][],k[],pp[];
int main()
{
int i,j,n,m,g;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,,sizeof(dp));
memset(k,,sizeof(k));
pp[] = ;
for(i = ; i <= ; i++)
pp[i] = pp[i-]*;
for(i = ; i <= n ;i++)
{
s[i] = ;
for(j = ;j <=m ;j++)
{
scanf("%d",&a[i][j]);
s[i]+=pp[j-]*a[i][j];
}
}
for(i = ; i < <<m ; i++)
if((((i>>)&(i))==||((i<<)&(i))==)&((i&s[])==i))
{
dp[][i]++;
num[][++k[]] = i;
}
for(i = ;i <= n ;i++)
{
for(j = ; j < <<m ; j++)
{
if((((j>>)&(j))==||(((j<<)&(j))==))&&((j&s[i])==j))
{
k[i]++;
for(g = ; g <= k[i-] ; g++)
{
int o = num[i%][g];
if((j&o)==)
dp[i][j]=(dp[i][j]+dp[i-][o])%mod;
}
num[(i+)%][k[i]] = j;
}
}
}
LL maxz=;
for(i = ; i < <<m ; i++)
maxz = (maxz+dp[n][i])%mod;
printf("%d\n",maxz);
}
return ;
}