【NOI2001】炮兵阵地

题面

https://www.luogu.org/problem/P2704

题解

状态压缩$dp$的经典题了吧。

因为直接压压不动，所以我写的是$hash$+记忆化。

#include<cstdio>
#include<iostream>
#define mod 5000007
#define ri register int
using namespace std;
struct Hash{
  long long val;
  int f;
} hash[5000010];
char mp[105][15];
int n,m,ans,val[1500],ss[105];

int value(int x){
  int ans=0;
  for (ri i=1;i<=m;i++) {
    if (x&(1<<(i-1))) ans++;
  }
  return ans;
}

bool can(int x,int cur) {
  if (x&(x<<1)) return 0;
  if (x&(x<<2)) return 0;
  if (x&(x>>1)) return 0;
  if (x&(x>>2)) return 0;
  if (x&ss[cur]) return 0;
  return 1;
}

int dfs(ri cur,ri s1,ri s2) {
  if (cur==n+1) return 0;

  long long yuan=(((s2<<m)+s1)<<7)+cur;
  ri hx=yuan%mod;

  if (hash[hx].val) {
    while (hash[hx].val && hash[hx].val!=yuan) {
      hx++;
      if (hx==mod) hx=0;
    }
    if (hash[hx].val==yuan) return hash[hx].f;
  }
  hash[hx].val=yuan;

  int as=0;
  for (ri i=0;i<=(1<<m)-1;i++) {
    if ((i&s1)==0 && (i&s2)==0  && can(i,cur)) as=max(as,val[i]+dfs(cur+1,i,s1));
  }
  hash[hx].f=as;
  return as;
}

int main() {
  string st;
  scanf("%d %d",&n,&m); getline(cin,st);
  for (ri i=0;i<(1<<m);i++) val[i]=value(i);
  for (ri i=1;i<=n;i++) {
    ss[i]=0;
    for (ri j=1;j<=m;j++) {
      mp[i][j]=getchar();
      if (mp[i][j]=='H') ss[i]|=(1<<(j-1)); 
    }
    getline(cin,st);
  }
  ans=dfs(1,0,0);
  cout<<ans<<endl;
}