AcWing 292 题解（动态规划—DP—状态压缩DP）

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 110, M = 1 << 10;
    
    int n, m;
    int g[N];
    int f[2][N][N];
    /*
    利用滚动数组，以为如果三维110数组的话会爆内存
    f[i][j][k]表示第i行状态为k, 第i - 1行状态为j的状态下已放置的炮台数量 
    */ 
    int cnt[N];
    vector<int> state;//记录所有合法情况 
    
    bool check(int state){
    	for(int i = 0; i < m; i ++ ){//总共有m列，即每一行有m个单元，遍历每个单元 
    		if((state >> i & 1) && (state >> i + 1 & 1 || state >> i + 2 & 1))
    			return false;
    	}
    	return true;
    } 
    
    int Cou