【浮*光】 #狀壓DP# NOI2001&洛谷p2704 炮兵陣地

【NOI2001&洛谷p2704】炮兵陣地

• 一個N*M的地圖，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。
• 在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）。
• 每個部隊能夠攻擊到的區域：沿橫向左右各兩格，沿縱向上下各兩格。
• 兩支炮兵部隊之間不能互相攻擊，即任何炮兵部隊都不在其他部隊的攻擊範圍内。
• 在整個地圖區域内最多能夠擺放多少我軍的炮兵部隊。

【思路分析】

用每個m位二進制數表示一行的狀态：

每個二進制數的第k位為1表示在第k列上放置部隊。

預處理出集合S(sum[ ])，儲存“相鄰兩個1的距離不小于3”的所有M位二進制數。

int sums[(1<<10)];
//sums[x]表示x的二進制表示中1的個數。（int）
           

bool vaild[109][1<<11];
           

vaild[i][x]表示滿足預處理條件的情況下，x的二進制表示中，

所有1的位置對應在地圖第i行中，都是能使用的平原。（bool）

↑↑↑【有障礙時】存儲行數，判斷該行某狀态是否成立。

也可以不使用，用a[109]記錄每行的初始可行狀态(是二進制數轉化為十進制的數)。

判斷的時候，隻用在每次循環時特判相對應的S&a[i]。 

int ff[109][1<<11][1<<11]; //2048*2048*109??? ---> 是以要用滾動數組啊qwq
//f[i][j][k]表示第i-1行的狀态是j，第i行狀态是k時，前i行最多放置的炮兵數。

int f[4][(1<<11)][(1<<11)]={0}; //【滾動數組】對于每一行，隻用記錄前兩行的狀态。
           

【代碼實作】

#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）

//bool vaild[109][1<<11];
//vaild[i][x]表示滿足預處理條件的情況下，x的二進制表示中，
//所有1的位置對應在地圖第i行中，都是能使用的平原。（bool）
//↑↑↑【有障礙時】存儲行數，判斷該行某狀态是否成立。
//也可以不使用，用a[109]記錄每行的初始可行狀态(是二進制數轉化為十進制的數)。
//判斷的時候，隻用在每次循環時特判相對應的S&a[i]。

//int ff[109][1<<11][1<<11]; //2048*2048*109??? ---> 是以要用滾動數組啊qwq
//f[i][j][k]表示第i-1行的狀态是j，第i行狀态是k時，前i行最多放置的炮兵數。

int f[4][(1<<11)][(1<<11)]={0}; //【滾動數組】對于每一行，隻用記錄前兩行的狀态。

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 QAQ

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]每次向前移一位
      a[i]+=(ss=='H'?1:0); //記錄障礙的位置
    }

  memset(sums,0,sizeof(sums));

  for(int i=0;i<(1<<m);i++) //對于每個狀态，記錄每行放置的部隊數
    sums[i]=getsum(i); //初始化sum數組

  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]; //第一行要特殊判定(因為沒有1-2=-1行)

  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是上一行,k是這一行
        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]);
        }
      }
    } 

  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]); //結束狀态可以是最後一行(編号n-1)的任何狀态
  
  cout<<anss<<endl;
  return 0;
}
           

                                                          ——時間劃過風的軌迹，那個少年，還在等你。