题目

传送门：QWQ

分析

看到$ M<=10 $考虑状压。

然后把每行都压一下，那么每个状态相关的就是上一行和上上行的状态。

然后枚举。

然后复杂度最坏是$ O(100 \times 1024^3) $的

仔细分析一下，有很多状态是无用的，但还是被判断了，比如$ 11111 $，显然不能做到不误伤。

那么我们把所有可能的状态拉出来（据说小于70？），即代码中的$ st $数组

然后用$ dp[i][j][k] $ 表示前i行上行状态st[j]本行状态st[k]的最大炮兵数量

然后就可以通过上行和上上行很快的更新了

最后统计答案时把最后一行每个位置都要算一下。

代码

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=;

int all[maxn], dp[][][], num[];

int ans=-1e9, ks=, n, m, st[maxn], sum[maxn], cnt;

char map[maxn][maxn];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        scanf("%s",map[i]);

        for(int j=;j<m;j++){

            if(map[i][j]=='H') all[i]|=(<<j);

        }

    }

    for(int i=;i<=;i++){

        for(int j=i;j;j>>=) if(j%) num[i]++;

    }

    for(int i=;i<(<<m);i++) //预处理出一行可能的状态

        if(!(i&(i<<)) && !(i&(i<<))) st[++cnt]=i,sum[cnt]=num[i];

    for(int i=;i<=cnt;i++) if(!(st[i]&all[])) dp[][][i]=sum[i];

    int ans=;

    //dp[i][j][k]前i行上行状态st[j]本行状态st[k]

    for(int i=;i<n;i++){

        for(int j=;j<=cnt;j++){

            for(int k=;k<=cnt;k++){

                if(st[j]&st[k]) continue;

                for(int l=;l<=cnt;l++){

                    if(!(st[j]&st[l])&&!(st[k]&st[l])&&!(st[l]&all[i+])){

                        dp[i+][k][l]=max(dp[i+][k][l], dp[i][j][k]+sum[l]);

                    }

                }

            }

        }

    }

    for(int i=;i<=cnt;i++)

        for(int j=;j<=cnt;j++)

            ans=max(ans,dp[n][i][j]);

    printf("%d",ans);

    return ;

}

巴特西

【POJ】1185 炮兵阵地（状压dp）

题目

传送门：QWQ

分析

代码

最新文章

热门文章