看到第一眼就发觉是壮压DP
然后就三进制枚举子集吧。
这题真是壮压入门好题。。。
对于dp[i][j] 表示第i行，j状态下前i行的分配方案数。
那么dp[i][j]肯定是从i-1行转过来的
那么由于不能挨着放，那么我们肯定是枚举i - 1行状态时不能包含j的任何一位。
那么只要令k = ((1 << n) - 1) ^ j，k中肯定就不包含j的位了
是这样枚举k的子集
int sub = k;
do
{
sub = k& (sub - 1);
}while(sub != k);
然后对每个子集，判断合法性，然后相加即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAXN 1005
#define INF 1000000000
using namespace std;
int dp[13][1 << 13];
int n, m;
int st[13];
int mod = 100000000;
bool ok(int s, int pos)
{
if((s | st[pos]) > st[pos]) return false;
for(int i = 0; i < n; i++)
if(s & (1 << i))
{
if(s & (1 << (i + 1))) return false;
}
return true;
}
int main()
{
int x;
scanf("%d%d", &m, &n);
for(int i = 1; i <= m; i++)
{
for(int j = 0; j < n; j++)
{
scanf("%d", &x);
if(x) st[i] |= (1 << j);
}
}
dp[0][0] = 1;
for(int i = 1; i <= m; i++)
{
for(int k = 0; k < (1 << n); k++)
{
int s = ((1 << n) - 1) ^ k;
if(ok(k, i))
{
//printf("%d %d
", k, s);
dp[i][k] += dp[i - 1][0];
for(int j = s; j; j = s & (j - 1))
{
if(ok(j, i - 1))
dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;
}
}
}
}
int ans = 0;
for(int i = 0; i < (1 << n); i++)
ans = (ans + dp[m][i]) % mod;
printf("%d
", ans);
return 0;
}