论状压记忆化搜索

其实非常简单，甚至比递推写法简单
比如P2704，递推做这个比较麻烦，但状压记搜强大

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int n,m,k[101];
char x;
bitset<10> bs;
int mem[1<<11][1<<11][101];
int dfs(unsigned f,unsigned ff,int l){if(l==n)return 0;if(mem[f][ff][l])return mem[f][ff][l];int ans=0;unsigned ym=k[l]&~f&~ff;for(unsigned i=ym;;i=(i-1)&ym){if(i&(i<<1))continue;if(i&(i<<2))continue;if(i&(i>>1))continue;if(i&(i>>2))continue;ans=max(ans,dfs(i,f,l+1)+__builtin_popcount(i));if(!i)break;}return mem[f][ff][l]=ans;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i=0;i<n;i++){for(int j=0;j<m;j++)cin >> x,bs[j]=x=='P'?1:0;k[i]=bs.to_ulong();}cout << dfs(0,0,0);return 0;
}