2016-02-23

状压DP

文章目录

原文地址:https://ngunauj.github.io

这里已POJ3254为例。POJ3254题目大意是在1的位置放牛，并且所放的牛不能相邻。
可根据行数分阶段，每个阶段的状态是根据上一阶段的状态得来的也就是 dp[i][s]=sum(dp[i][t])

/* ***********************************************
Author        :guanjun
Created Time  :2015/8/1 9:54:13
File Name     :1.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 100000000
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const int N=13;
const int M=1<<N;
const double eps=1e-5;
using namespace std;
bool cmp(int a,int b){
    return a>b;
}
int n,m;
int st[M],mp[M];//分别存储每一行的状态和给出的状态
int dp[N][M];//表示第i行状态为j时可以放的牛的数量
bool judge1(int x){
    return (x&(x<<1));//判断两头牛是否相邻 移动一位&
}
bool judge2(int i,int x){
    return (mp[i]&st[x]);//判断当前的状态是否在 已经给出的状态中
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    while(cin>>n>>m){
        //每一行可能的状态 处理出来
        //dp[i][s]=sum(dp[i-1][t]);
        cle(dp);
        cle(st);
        cle(mp);
        int x;
        for(int i=1;i<=n;i++){
            for(int j=0;j<m;j++){
                cin>>x;
                if(x==0)//为什么当x==0时处理呢？因为存在这一行都不放牛的情况
                    mp[i]+=(1<<j);//存储当前行的状态
            }
        }
        //初始化满足的在非约束条件下的每行可能的状态
        int k=0;
        for(int i=0;i<(1<<m);i++){
            if(!judge1(i))
                st[k++]=i;//存储满足牛不相邻的状态(有的题目是通过dfs找的)
                //k的值也就是 满足牛不相邻的状态的个数
        }
        //dp 边界的处理
        //因为dp的时候要涉及到上一行 所以这里先处理出第一行
        for(int i=0;i<k;i++){
            if(!judge2(1,i))
                dp[1][i]=1;
        }
        //正式dp
        for(int i=2;i<=n;i++){
            for(int j=0;j<k;j++){
                if(!judge2(i,j)){
                    for(int t=0;t<k;t++){
                        if(!judge2(i-1,t)){
                            if(!(st[j]&st[t])){//不相互包含
                                dp[i][j]+=dp[i-1][t];
                            }
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<k;i++){
            ans+=dp[n][i];
            ans%=mod;
        }   
        printf("%d\n",ans);
    }
    return 0;
}