[luogu P2704] 炮兵阵地

题目描述

点击此处查看题目描述

解题过程

思路

这道题的列数的数据范围很小，我们考虑用状态压缩进行动态规划

流程

设 $a[i]$ 表示第 $i$ 行的地形(0101用十进制存储) 先存储二进制地形，山峰 $H$ 表示 $1$ ，平原就不用管，表示 $0$

设 $dp[i][j][k]$ 表示在上一行的状态为 $k$ 时，第 $i$ 行的状态为 $j$ 时的最大炮台数
直接暴力往上枚举整个状态的复杂度是 $O(2^{3m}?n)$ 很显然会超时

我们可以提前处理炮台互不冲突的状态

设 $F[i]$ 表示第 $i$ 种炮台互不冲突的状态，设 $D[i]$ 表示当前 $F[i]$ 状态表示的炮台数

求 $D[i]$ 比较简单：

int get_num (int x) {
    int countx = 0;while(x){
    countx ++;x = x