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 閱讀(592)
評論(0) 編輯 收藏 引用 所屬分類:
poj