P1896

这是一道状压dp题（状态压缩）。It`s the first time that I had accepted a zhuangya dp problem！

把一行每一位放与不放用二进制中的01表示，状态压缩就是将一行的状态用一个二进制数表示。

解法在代码的注释中：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n,m,all;bool f1[513];//表示一行i状态可不可以放 bool f2[513][513];//表示相邻两行i和j状态可不可放int cnt[513];int f[20][101][513];//f[i][j][k]表示放到第i行,放了j个王,当前这行状态为k,的方案数 void pre(){ for(int i=0;i
            
             >1))==0){ f1[i]=1; for(int x=i;x;x=x>>1) cnt[i]+=(x&1);//这个数转为二进制有多少个1 } for(int i=0;i
             
              >1))==0)&&((j&(i>>1))==0)&&((j&i)==0)) f2[i][j]=1;} int main(){ //freopen("a.in","r",stdin); scanf("%d%d",&n,&m); all=(1<