POJ 3254 Corn Fields 状压DP

古城微笑少年丶 2022-07-24 07:07 90阅读 0赞

题目链接：[http://poj.org/problem?id=3254][http_poj.org_problem_id_3254]

题目大意：给你一个矩阵，矩阵由0和1组成，你要找出矩阵中所有的1的不同组合，但是不能有两个1相邻

比如：  
1 1 1  
0 1 0

假设1的标号为 1 2 3  
4  
则1的个数为0的组合有1种  
个数为1的组合有4种 1 ，2 ，3 ，4  
个数为2的组合有3种1 3，1 4，3 4  
个数为3的组合有1种 1 3 4

解题思路：可以在行之间DP，找出某一行的所有合法状态，因为此行的任意一个合法状态都可以由上一行的某几个合法状态转移。  
判断是否能转移只要两个状态按位与一下为0就可以转移了。  
每一个合法状态都要加上上一行所有满足转移条件的合法状态。  
最后答案就是把最后一行的得到数相加即可，注意因为自己本身也算一个合法状态所以，所以初始的0要赋值为1。

代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    int m,n;
    
    bool legalsubstring(int ori,int x)
    {
        int poi=-2;
        for(int i=0;i<n;i++)
        {
            int q=1<<i&x;
            int q1=1<<i&ori;
            if(q&&(i-poi)==1) return false;
    
            if( q>q1 ) return false;
            if(q) poi=i;
    
    
        }
        return true;
    
    }
    
    int main()
    {
    
        RII(m,n);
        int ma[20];
        mem(ma);
    
    
        for(int i=0;i<m;i++)
            for(int j=n-1;j>=0;j--)
                {
                    int a;
                    RI(a);
                    ma[i]|=a<<j;
                }
    
        int dp[15][1<<12];
        mem(dp[0]);
    
        int legalsub[15][1<<12];
    
        for(int i=0;i<m;i++)
        {
            int poi=1;
            for(int j=0;j<=ma[i];j++)
            {
                if(legalsubstring(ma[i],j))  legalsub[i][poi++]=j;
            }
            legalsub[i][0]=poi;
        }
    
        for(int i=1;i<legalsub[0][0];i++)
           {
               dp[0][legalsub[0][i]]=1;
    
           }
    
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<legalsub[i][0];j++)
            {
                for(int k=1;k<legalsub[i-1][0];k++)
                {
                    if((legalsub[i][j]&legalsub[i-1][k])==0)
                    {
                        dp[i][legalsub[i][j]]+=dp[i-1][legalsub[i-1][k]];
                        dp[i][legalsub[i][j]]%=100000000;
                    }
    
                }
            }
        }
        int ans=0;
        for(int i=1;i<legalsub[m-1][0];i++)
        {
            ans+=dp[m-1][legalsub[m-1][i]];
            ans%=100000000;
        }
        printf("%d\n",ans);
    
    
    
        return 0;
    }

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