dp[i][j]:1行到第i行的状态为j时最多的方法数
从第0行一直推到第n行
以下是比较简单的解法
#include <iostream>
#define MAX 4200
using namespace std;
int state[MAX], len;
int dp[14][MAX], ibit[MAX][14], t[14], n, m;
//dp[i][j]:1行到第i行的状态为j时最多的方法数
//ibit[i][j]：i状态的第j位为多少。(对于非2进制比较好用)
//t[i]:第i位的基数
int a[14][14];
void dfs1(int j, int to)
{
if(j >= m){
state[len++] = to;
return ;
}
if(j <= m-1)
dfs1(j+2, to+t[j]);
dfs1(j+1, to);
}
void pro_process()
{
len = 0;
dfs1(0, 0);
}
void dfs(int i, int j, int from, int to)
{
if(j >= m){
dp[i][to] += dp[i-1][from];
if(dp[i][to] >= 100000000)
dp[i][to] = dp[i][to]%100000000;
return;
}
if(j <= m-1){
if(ibit[from][j] == 0 && a[i][j])
dfs(i, j+2, from, to+t[j]);
}
dfs(i, j+1, from, to);
}
void slove()
{
int i, j;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
pro_process();
for(i = 1; i <= n; i++){
for(j = 0; j < len; j++){
dfs(i, 0, state[j], 0);
}
}
int ans = 0;
for(i = 0; i < MAX; i++)
ans += dp[n][i];
ans = ans%100000000;
cout << ans << endl;
}
int main()
{
int i, j, k;
for(i = 0; i < MAX; i++){
j = 0;
k = i;
while(k > 0){
ibit[i][j] = k%2;
k = k/2;
j++;
}
}
t[0] = 1;
for(i = 1; i < 14; i++)
t[i] = t[i-1]*2;
while(cin >> n >> m){
for(i = 1; i <= n; i++)
for(j = 0; j < m; j++)
cin >> a[i][j];
slove();
}
return 0;
}
经过DieIng大牛的指点，对其进行优化，速度快了10来倍，但是还是跑了16ms
#include <iostream>
#define MAX 4200
using namespace std;
int state[MAX], len;
//记录可行的状态
int ft[MAX][MAX], ftn[MAX];
//ft[i][j]：从上一行为状态i到这一行的第j个可行状态为ft[i][j]
//ftn[i]:从上一行为状态i到这一行的可行状态数
int dp[14][MAX], ibit[MAX][14], t[14], n, m;
//dp[i][j]:1行到第i行的状态为j时最多的方法数
//ibit[i][j]：i状态的第j位为多少。(对于非2进制比较好用)
//t[i]:第i位的基数
int p, b[14];
void dfs1(int j, int to)
{
if(j >= m){
state[len++] = to;
return ;
}
if(j <= m-1)
dfs1(j+2, to+t[j]);
dfs1(j+1, to);
}
void dfs2(int j, int from, int to, int i)
{
if(j >= m){
ft[from][ftn[i]++] = to;
return ;
}
if(j <= m-1){
if(ibit[from][j] == 0)
dfs2(j+2, from, to+t[j], i);
}
dfs2(j+1, from, to, i);
}
void pro_process()
{
len = 0;
dfs1(0, 0);
int i;
for(i = 0; i < len; i++){
ftn[i] = 0;
dfs2(0, state[i], 0, i);
}
}
void slove()
{
int i, j, k, st, sk;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
pro_process();
for(i = 1; i <= n; i++){
for(j = 0; j < len; j++){
st = state[j];
for(k = 0; k < ftn[j]; k++){
sk = ft[st][k];
if((sk&b[i]) == sk)
dp[i][sk] += dp[i-1][st];
if(dp[i][sk] > 100000000)
dp[i][sk] %= 100000000;
}
}
}
int ans = 0;
for(j = 0; j < len; j++)
ans += dp[n][state[j]];
ans %= 100000000;
cout << ans << endl;
}
int main()
{
int i, j, k;
for(i = 0; i < MAX; i++){
j = 0;
k = i;
while(k > 0){
ibit[i][j] = k%2;
k = k/2;
j++;
}
}
t[0] = 1;
for(i = 1; i < 14; i++)
t[i] = t[i-1]*2;
while(cin >> n >> m){
for(i = 1; i <= n; i++){
b[i] = 0;
for(j = 0; j < m; j++){
cin >> p;
b[i] += p*t[j];
}
}
slove();
}
return 0;
}
posted on 2009-05-15 21:17
longshen 阅读(571)
评论(0) 编辑 收藏 引用 所属分类:
poj