【浮*光】#状态压缩# 状压DPの相关练习题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

//用每个m位二进制数表示一行的状态：
//每个二进制数的第k位为1表示在第k列上放置部队。

/*【p2704】炮兵阵地
一个N*M的地图，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。
每个部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
两支炮兵部队之间不能互相攻击，即任何炮兵部队都不在其他部队的攻击范围内。
在整个地图区域内最多能够摆放多少我军的炮兵部队。*/

//预处理出集合S，储存“相邻两个1的距离不小于3”的所有M位二进制数。

int sums[(1<<10)]; //sums[x]表示x的二进制表示中1的个数//int ff[109][1<<11][1<<11]; //2048*2048*109??? ---> 所以要用滚动数组啊qwq
//f[i][j][k]表示第i-1行的状态是j，第i行状态是k时，前i行最多放置的炮兵数。

int f[3][(1<<11)][(1<<11)]={0}; //【滚动数组】记录前两行的状态即可，即(%3=)0,1,2 。

int n,m,a[109],anss=0; //a[109]记录每行的初始可行状态(是二进制数转化为十进制的数)

void reads(int &x){ int fx=1;x=0;char s=getchar();
  while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();}
  while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; }

int getsum(int S){ //当前状态 S 里面包含几个 1
  int tot=0; while(S){if(S&1) tot++; S>>=1;} return tot;
} //【坑点！！】这个一定要写成函数，要不然会TLE...

int main(){
  reads(n); reads(m); char ss;
  
  for(int i=0;i<n;i++) //注意，状压DP中最好都用0开始
    for(int j=0;j<m;j++) //用a[i]记录每行的初始可行状态
      cin>>ss,a[i]<<=1,a[i]+=(ss=='H'?1:0); 
    //二进制数a[i]每次向前移一位，记录第i行中障碍的位置

  memset(sums,0,sizeof(sums)); //记录每种行状态要放置的部队数
  for(int i=0;i<(1<<m);i++) sums[i]=getsum(i);

  for(int i=0;i<(1<<m);i++) //【预处理】初始化第一行(行数编号是0)
    if(!(i&a[0] || (i&(i<<1)) || (i&(i<<2)))) //判断‘行放置情况’有没有冲突
      f[0][i][0]=sums[i]; //第一行要特殊判定，相当于赋初始值

  for(int j=0;j<(1<<m);j++) //【预处理】初始化第二行(行数编号是1)
    for(int k=0;k<(1<<m);k++) //j是上一行,k是这一行
      if(!(j&k || j&a[0] || k&a[1] || (j&(j<<1)) || (j&(j<<2)) 
          || (k&(k<<1)) || (k&(k<<2)) ) )
        f[1][j][k]=sums[k]+sums[j]; //第二行要特殊判定(因为没有2-2=0行)

  for(int i=2;i<n;i++) //枚举行数
    for(int j=0;j<(1<<m);j++){ //【预处理】“相邻两个1的距离不小于3”的所有M位二进制数
      if(j&a[i-1] || (j&(j<<1)) || (j&(j<<2))) continue;  //‘行放置状态’冲突
      for(int k=0;k<(1<<m);k++){ //j是上一行(i-1),k是这一行(i)
        if(k&a[i] || j&k || (k&(k<<1)) || (k&(k<<2))) continue; //特判
        for(int FL=0;FL<(1<<m);FL++){ //FL是上上一行
          if(FL&j || FL&k || FL&a[i-2] || (FL&(FL<<1)) || (FL&(FL<<2))) continue;   
          f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][FL][j]+sums[k]); //转移:max放置数
        }
      }
    } 

  for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) anss=max(anss,f[(n-1)%3][j][k]);
  cout<<anss<<endl; return 0; //倒数两行可以是任意状态(可行才会有值),求出最终的max放置个数

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

//用每个m位二进制数表示一行的状态：
//每个二进制数的第k位为1表示在第k列上放置部队。

/*【p2704】炮兵阵地
一个N*M的地图，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。
每个部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
两支炮兵部队之间不能互相攻击，即任何炮兵部队都不在其他部队的攻击范围内。
在整个地图区域内最多能够摆放多少我军的炮兵部队。*/

int sums[(1<<10)]; //sums[x]表示x的二进制表示中1的个数

int f[3][(1<<11)][(1<<11)]={0}; //【滚动数组】记录前两行的状态即可，即(%3=)0,1,2 。

int n,m,a[109],anss=0; //a[109]记录每行的初始可行状态(是二进制数转化为十进制的数)

void reads(int &x){ int fx=1;x=0;char s=getchar();
  while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();}
  while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; }

int get_cnt(int S){ //当前状态 S 里面包含几个 1
  int tot=0; while(S){if(S&1) tot++; S>>=1;} return tot;
} //【坑点！！】这个一定要写成函数，要不然会TLE...

int main(){
  reads(n); reads(m); char ss;

  for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>ss,a[i]<<=1,a[i]+=(ss=='H'?1:0);
  
  for(int i=0;i<(1<<m);i++) sums[i]=get_cnt(i); //先处理出sums

  for(int i=0;i<(1<<m);i++) for(int j=0;j<(1<<m);j++)
    if( ! ( (i&a[1]) || (j&a[0]) || (i&j) || (i&(i<<1)) //只需预处理第二行
      || (i&(i<<2)) || (j&(j<<1)) || (j&(j<<2)) ) ) f[1][i][j]=sums[j]+sums[i];
  
  for(int i=2;i<n;i++) //注意这里要从i=2开始
    for(int j=0;j<(1<<m);j++){ //上一行
      if(j&a[i-1]||(j&(j<<1))||(j&(j<<2))) continue;
      for(int k=0;k<(1<<m);k++){ if(j&k) continue;
        if(k&a[i]||(k&(k<<1))||(k&(k<<2))) continue;
        for(int LS=0;LS<(1<<m);LS++){ if((j&LS)||(k&LS)) continue;
          if(LS&a[i-2]||(LS&(LS<<1))||(LS&(LS<<2))) continue;
          f[i%3][k][j]=max(f[i%3][k][j],f[(i-1)%3][j][LS]+sums[k]); }
      }
  }

  for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) anss=max(anss,f[(n-1)%3][j][k]);
  cout<<anss<<endl; return 0; //倒数两行可以是任意状态(可行才会有值),求出最终的max放置个数

}