「NOI 2010」炮兵阵地

「Link」

首先观察炮的攻击范围，左右上下完全对称

也就是说，A 打不到 B 和 B 打不到 A 是等价的，于是就考虑左边和上面

一行一行地考虑，正在考虑第 $i$ 行

一行内部炮冲突的问题是容易解决的

考虑上几行对第 $i$ 行，第 $j$ 列能不能放的的影响有 $(i-1,j)$ 和 $(i-2,j)$

很自然的，可以定义出压缩的状态

• $0$ 下一行可以放（当然还要综合地形考虑 ）
• $1$ 下一行不可以放
• $2$ 下两行不可以放

如果直接暴力枚举会有大量冗余，考虑 dfs 递推

假设当前已处理完 $f_{i,j}$ $i$ 为行号，$j$ 为状态，$k$ 为列号，$v$ 表示递推的状态

• $j_k=2\rightarrow v_k = 1$
• $j_k=1\rightarrow v_k = 0$
• $g_{i,k}=H\rightarrow v_k = 0$
• 其他情况 $v_k=0/2$

行内部的冲突问题，相信各位肯定想想就知道

程序存在大量优化的空间（

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

const int p[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441};

const int N = 101, M = 11;
int g[N], f[2][531441];
std::vector<int> s;
int *cur;
int n, m, prev, v[M];
// #define dbg(...) fprintf(stderr, __VA_ARGS__);
#define dbg(...)

void dfs(int status, int i, int lst, int cnt) {
    if (i == m) {
        dbg("reach\n");
        cur[status] = std::max(cur[status], cnt + prev);
        return;
    }
    if (v[i] == 1 || v[i] == 0)
        dfs(status + v[i] * p[i], i + 1, lst, cnt);
    else if (lst + 2 < i) {
        dfs(status + 2 * p[i], i + 1, i, cnt + 1);
        dfs(status, i + 1, lst, cnt);
    } else {
        dfs(status, i + 1, lst, cnt);
    }
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    cin >> n >> m;
    std::memset(f, -1, sizeof(f));
    f[0][0] = 0;
    for (int i = 0; i < p[m]; ++i) {
        int valid = 1;
        for (int x = i, j = 0, lst = -5; j < m; ++j, x /= 3)
            if (x % 3 == 2) {
                if (lst + 2 < j)
                    lst = j;
                else {
                    valid = 0;
                    break;
                }
            }
        if (valid) s.push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            g[j] = (c == 'H');
        }
        cur = f[(i + 1) & 1];
        std::memset(cur, -1, sizeof(f) / 2);
        for (auto j : s) {
            if (f[i & 1][j] == -1) continue;
            prev = f[i & 1][j];
            for (int k = 0, x = j; k < m; ++k, x /= 3) {
                if (x % 3 == 2)
                    v[k] = 1;
                else if (x % 3 == 1 || g[k])
                    v[k] = 0;
                else
                    v[k] = -1;
                dbg("%3d", v[k]);
            }
            dbg("\n");
            dfs(0, 0, -5, 0);
        }
    }
    int ans = -1;
    for (auto j : s) ans = std::max(ans, f[n & 1][j]);
    cout << ans;
    return 0;
}