NC16886 炮兵阵地

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int dp[108][1 << 10][1 << 10];
int ma[108][18];
int n, m;
vector<int> sta[108], pao[108];
int st[18];
void dfs(int r, int p)
{
    if (p == m + 1)
    {
        int s = 0, t = 0;
        bool fl = false;
        for (int i = 1; i <= m; i++)
        {
            s <<= 1;
            if (st[i]) s |= 1, t++;
        }
        for (int j = 1; j <= 2; j++)
            if ((s << j) & s || (s & (s >> j)))
            {
                fl = true;
                break;
            }
        if (!fl)
        {
            sta[r].push_back(s);
            pao[r].push_back(t);
        }
        return;
    }
    dfs(r, p + 1);
    if (ma[r][p])
    {
        st[p] = 1;
        dfs(r, p + 1);
        st[p] = 0;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c; cin >> c;
            if (c == 'P') ma[i][j] = 1;
        }
    sta[0].push_back(0), pao[0].push_back(0);
    for (int i = 1; i <= n; i++) dfs(i, 1);
    for (int i = 0; i < pao[1].size(); i++) dp[1][0][i] = pao[1][i];
    for (int i = 0; i < pao[1].size(); i++)
        for (int j = 0; j < pao[2].size(); j++)
        {
            if (sta[1][i] & sta[2][j]) continue;
            dp[2][i][j] = max(dp[2][i][j], dp[1][0][i] + pao[2][j]);
        }
    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j < sta[i - 2].size(); j++)
        {
            for (int k = 0; k < sta[i - 1].size(); k++)
            {
                if (sta[i - 2][j] & sta[i - 1][k]) continue;
                for (int l = 0; l < sta[i].size(); l++)
                {
                    if (sta[i][l] & sta[i - 1][k]) continue;
                    if (sta[i][l] & sta[i - 2][j]) continue;
                    dp[i][k][l] = max(dp[i][k][l], dp[i - 1][j][k] + pao[i][l]);
                }
            }
        }
    }
    int ans = 0;
    for(int j  = 0; j < sta[n - 1].size(); j++)
    for (int i = 0; i < sta[n].size(); i++)
        ans = max(ans, dp[n][j][i]);
    printf("%d", ans);
    return 0;
}