P7689

Bzw's Blog / 2023-05-06 / 原文

类似 P2704 [NOI2001] 炮兵阵地这道题，考虑用 \(f_{i,j,k}\) 表示到第 \(i\) 行，该行的状态为 \(j\)，第 \(i-1\) 行的状态为 \(k\) 的方案数，但是时间复杂度显然不对，考虑状态压缩。

我们发现第 \(i\) 行的放置方案只与 \((i,j)\) 是否能放置芯片有关，考虑用高进制来表示状态。

首先将 \((2\times 3)\) 和 \((3\times 2)\) 的芯片分别表示为：

\[\begin{aligned} &1 \quad 1 \quad 1\\ &0 \quad 0 \quad 0\\ \end{aligned} \]

和

\[\begin{aligned} &2 \quad 2\\ &1 \quad 1\\ &0 \quad 0\\ \end{aligned} \]

设 \(a_{i,j}\) 表示 \((i,j)\) 所填的值，那么有：

若 \(a_{i,j}\) 的值为 \(2\)，则 \(a_{i+1,j}\) 的值为 \(1\)。
若 \(a_{i,j}\) 的值为 \(1\)，则 \(a_{i+1,j}\) 的值为 \(0\)。
若 \((i,j)\) 已经损坏，则 \(a_{i-1,j}=0\)，且 \(a_{i,j}=0\)。

那么以 \((i,j)\) 为左上角放置一个 \(2\times 3\) 的芯片就是将 \(a_{i,j}=a_{i,j+1}=a_{i,j+2}=1\)、\(a_{i+1,j}=a_{i+1,j+1}=a_{i+1,j+2}=0\)。

以 \((i,j)\) 为左上角放置一个 \(3\times 2\) 的芯片就是将 \(a_{i,j}=a_{i,j+1}=2\)、\(a_{i+1,j}=a_{i+1,j+1}=1\)、\(a_{i+2,j}=a_{i+2,j+1}=0\)。

状态转移方程容易写出，但是不容易递推实现，可以考虑 \(\texttt{DFS}\) 进行转移。

由于内存只有 \(\texttt{8.00 MB}\)，所以要用滚动数组，注意状态转移数组的清空。

#include <bits/stdc++.h>
using std::cin;    using std::cout;
using std::printf; using std::scanf;
template<typename T> inline void Max(T &x, const T &y){x<y?x=y:0;return;}
const int N=3e2+1;

int Pow3[55];
void init_pow_base_3(int tt){
  Pow3[1]=1;
  for(int i=2; i<=tt+1; i++)
    Pow3[i]=Pow3[i-1]*3;
}

int n, m, K, vis[N][55], f[2][200000];

int getith(int F, int pos){return (F/Pow3[pos])%3;}
int allow(int I, int F, int Pos){return getith(F, Pos)==0&&vis[I][Pos]==0;}

void dfs(int I, int Last, int F, int Pos, int Cnt){
  if(Pos==m+1) return Max(f[I&1][F], f[(I-1)&1][Last]+Cnt);
  int L=getith(Last, Pos);
  if(L!=0){
    if(vis[I][Pos])return;
    dfs(I, Last, F+Pow3[Pos]*(L-1), Pos+1, Cnt);
    return;
  }
  else{
    dfs(I, Last, F, Pos+1, Cnt);

    if(Pos<m&&allow(I, Last, Pos)&&allow(I, Last, Pos+1))
      dfs(I, Last, F+2*(Pow3[Pos]+Pow3[Pos+1]), Pos+2, Cnt+1);

    if(Pos<m-1&&allow(I, Last, Pos)&&allow(I, Last, Pos+1)&&allow(I, Last, Pos+2))
      dfs(I, Last, F+1*(Pow3[Pos]+Pow3[Pos+1]+Pow3[Pos+2]), Pos+3, Cnt+1);
  }
  return;
}
int main(){
  int T;
  scanf("%d", &T);
  init_pow_base_3(11);

  while(T--){
    scanf("%d %d %d", &n, &m, &K);
    memset(vis, 0, sizeof vis);
    for(int i=1, a, b; i<=K; i++)
      scanf("%d %d", &a, &b), vis[a][b]=1;

    memset(f, -0x3f3f3f3f, sizeof f);
    f[0][0]=0;

    for(int i=1; i<=n; i++){
      for(int j=0; j<Pow3[m+1]; j++)
        f[i&1][j]=-0x3f3f3f3f;

      for(int j=0; j<Pow3[m+1]; j++)
        if(f[(i-1)&1][j]>=0) dfs(i, j, 0, 1, 0);
    }

    cout<<f[n&1][0]<<'\n';
  }
  return 0;
}