Mondriaan's Dream POJ - 2411(状压dp)-白红宇

Mondriaan's Dream POJ - 2411(状压dp)

阅读量：4702 次

发布时间：2019-06-09

本文共 986 字，大约阅读时间需要 3 分钟。

这里是链接

dp[i][j]表示第i行状态为j时的方案数

在位置(i, j) 如果我们选择横着贴砖，那么将(i, j), (i, j+1)都填写成1，如果竖着贴砖，我们将(i,j)填写成0，将(i+1, j)填写成1.

及0是对下一行的状态有影响，1为没有

枚举每一种状态判断合法性

剪枝：如果上一行的状态数为0，直接continue

//#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define All L,R#define int long longusing namespace std;const int maxn=1e4+10;int n,m;long long dp[15][3005];int Cheek(int now){ int i=0; while(i
               
                n) swap(n,m); int M=(1<