POJ 3254 Corn Fields

http://poj.org/problem?id=3254
[DP]

覺得難過QQ

只好來寫水題QQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#define MOD 100000000
using namespace std;
int main()
{
int M, N;scanf("%d %d", &M, &N);
int line[100];
for(int lx = 0;lx < M;lx++){
line[lx] = 0;
for(int ly = 0;ly < N;ly++){
int inp;scanf("%d", &inp);
line[lx] = line[lx]*2 + inp;
}
}
int dp[14][1<<12];
for(int lx = 0;lx < (1<<N);lx++)
dp[0][lx] = ((lx|line[0])^line[0]) == 0 and ((lx>>1)&(lx)) == 0;
for(int lm = 1;lm < M;lm++){
for(int lx = 0;lx < (1<<N);lx++)
if(((lx|line[lm])^line[lm]) == 0 and ((lx>>1)&(lx)) == 0)
for(int ly = 0;ly < (1<<N);ly++){
dp[lm][lx] += dp[lm-1][ly]*((lx&ly) == 0);
dp[lm][lx] %= MOD;
}
}
int cnt = 0;
for(int lx = 0;lx < (1<<N);lx++)
cnt = (cnt +dp[M-1][lx])%MOD;
printf("%d\n", cnt);
return 0;
}