【POJ】1185 炮兵阵地(状压dp)

2018-06-26 来源: noble_(noblex) 发布在  https://www.cnblogs.com/noblex/p/9231600.html

题目

传送门: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;
;
][][], num[];
, n, m, st[maxn], sum[maxn], cnt;
char map[maxn][maxn];
int main(){
    scanf("%d%d",&n,&m);
    ;i<=n;i++){
        scanf("%s",map[i]);
        ;j<m;j++){
            <<j);
        }
    }
    ;i<=;i++){
        ) ) num[i]++;
    }
    ;i<(<<m);i++) //预处理出一行可能的状态
        )) && !(i&(i<<))) st[++cnt]=i,sum[cnt]=num[i];
    ;i<=cnt;i++) ])) dp[][][i]=sum[i];
    ;
    //dp[i][j][k]前i行上行状态st[j]本行状态st[k]
    ;i<n;i++){
        ;j<=cnt;j++){
            ;k<=cnt;k++){
                if(st[j]&st[k]) continue;
                ;l<=cnt;l++){
                    ])){
                        dp[i+][k][l]=max(dp[i+][k][l], dp[i][j][k]+sum[l]);
                    }
                }
            }
        }
    }
    ;i<=cnt;i++)
        ;j<=cnt;j++)
            ans=max(ans,dp[n][i][j]);
    printf("%d",ans);
    ;
}

相关文章