原题链接
\(这道题运用到了状态压缩dp的知识\)
\(主要作用为使用二进制中的!(i&i>>1)来表示左右一个是否能够互相攻击到 !(i&i>>2)来表示左右两格能否攻击到\)
\(对于上下的两格 我们考虑维护一个f[i][a][b] i表示当前为第几行 a表示第二行的数 b表示第一行的数\)
\(对于每个f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]])num[s[a]]代表当前行选取a能获得的数！\)
\(f[i-1][b][c]代表上一行选取 b c获得的最大值\)
\(判断能否选取的条件为\)
\(!(s[a]&s[b])&&!(s[a]&s[c])&&!(s[b]&s[c])&&(g[i]&s[a])==s[a]&&(g[i-1]&s[b])==s[b]\)
\(简单操作就不多赘述了\)
\(code：\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
const int N=110,M=1<<10;
int n,m;
int g[N];
int cnt;
vector<int>s;
int num[M];
int f[N][M][M];
void solve() {
cin>>n>>m;
// vector ch(n+1,vector<char>(m+1));
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
char ch;
cin>>ch;
if(ch=='P')g[i]|=1<<(m-j-1);
}
}
for(int i=0;i<(1<<m);i++){
if(!(i&i>>1)&&!(i&i>>2)){
s.pb(i);
for(int j=0;j<m;j++){
num[i]+=(i>>j)&1;
}
}
}
cnt=s.size();
for(int i=1;i<=n+2;i++){
for(int a=0;a<cnt;a++){
for(int b=0;b<cnt;b++){
for(int c=0;c<cnt;c++){
if(!(s[a]&s[b])&&!(s[a]&s[c])&&!(s[b]&s[c])&&(g[i]&s[a])==s[a]&&(g[i-1]&s[b])==s[b]){
f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]]);
}
}
}
}
}
cout<<f[n+2][0][0];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--);
solve();
}