[NOI2001] 炮兵阵地

archer233 / 2024-10-11 / 原文

原题链接
$这道题运用到了状态压缩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();
}