状态压缩DP 洛谷2704 炮兵阵地

传送门

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 105

const int mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int N, M;
char f[15];
int cnt[105];
int king[105][MAXN];
int state[105][MAXN];
int dp[105][MAXN][MAXN];

void init(int k) {
    for (int i = 0; i < M; i++) {
        cin >> f[i];
        f[i] = f[i] == 'H' ? '0' : '1';
    }
    f[M] = '\0';
    int temp = strtol(f, NULL, 2);
    int tot = (1 << M) - 1;
    for (int i = 0; i <= tot; i++) {
        if ((i | temp) == temp) {
            if (!(i & (i << 1) || i & (i << 2) || i & (i >> 1) || i & (i >> 2))) {
                state[k][++cnt[k]] = i;
                int o = i;
                while (o) {
                    king[k][cnt[k]] += o & 1;
                    o >>= 1;
                }
            }
        }
    }
}

int main(void)
{
    freopen("data.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        init(i);
    cnt[0] = 1;
    state[0][1] = 0;

    for (int i = 1; i <= cnt[1]; i++)
        dp[1][i][1] = king[1][i];

    for (int i = 2; i <= N; i++) {
        for (int o = 1; o <= cnt[i - 2]; o++) {
            for (int j = 1; j <= cnt[i - 1]; j++) {
                for (int k = 1; k <= cnt[i]; k++) {
                    if (!(state[i - 2][o] & state[i][k] || state[i - 1][j] & state[i][k])) {
                        dp[i][k][j] = max(dp[i][k][j], dp[i - 1][j][o] + king[i][k]);
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= cnt[N - 1]; i++) {
        for (int j = 1; j <= cnt[N]; j++) {
            ans = max(ans, dp[N][j][i]);
        }
    }

    cout << ans << endl;

    freopen("CON", "r", stdin);
    system("pause");
    return 0;
}