State compression DP AcWing 291. Mondrian's dream

Original link

AcWing 291. Mondrian's dream

Algorithm tags

Dynamic programming State compression DP

Ideas

Specific ideas

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 12, M = 1 << N;
int f[N][M], st[M];
vector<int> sta[M];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    while(n=read(), m=read(), n||m){
    	// Preprocessing : Judge whether the status of the consolidated column is legal 
		// If a row of the merged column is 1 It means horizontal , yes 0 Indicates vertical placement 
		// If there is no continuous odd number of merged columns 0, It is the state of Taiwan France 
        rep(i, 0, 1<<n){
        	// cnt  For how many consecutive 0
            int cnt=0;
            st[i]=true;
            rep(j, 0, n){
                if(i>>j&1){//  If it is 1
                    if(cnt&1){//  If it's continuous 0 The number of is odd 
                        st[i]=false;//  Record i illegal 
                        cnt=0;
                    }
                }
                else{//  If it is 1,  Record 0 The number of 
                    cnt++;
                }
            }
            //  Handle high order 0 The number of   With 4 For example  0100  It is also an illegal number 
            if(cnt&1){
                st[i]=false;
            }
        }
        // State calculation 
        memset(f, 0, sizeof f);
        //  The first 0 It is a legal scheme that columns are not placed horizontally 
        f[0][0]=1;
        rep(i, 1, m+1){// Stage :  Enumerating columns 
            rep(j, 0, 1<<n){// state : Enumerate the i The state of the column 
                rep(k, 0, 1<<n){// state : Enumerate the 11 The state of the column 
                	// j & k == 0  Express  i  Column sum  i - 1 List the same row and poke it out at the same time 
                    // st[j | k] == 1  Express   stay  i  Column status  j, i - 1  Column status  k  Is legal .
                    //  The two columns are compatible : There is no overlap 1, There are no consecutive odd days 

                    if((j&k)==0&&st[j|k]){
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        // The first m The columns are not placed horizontally ,  That is the answer. 
        printf("%lld\n", f[m][0]);
    }
    return 0;
}     

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support