求助状压 dp

样例输出 13

#include <bits/stdc++.h>

using namespace std;

long long n, m;
bool a[102][12];
char S[12];
long long f[102][(1 << 10) + 2][(1 << 10) + 2];

long long dkw (long long n, long long k) {
    n >>= k;
    return n & 1;
}

bool inlaw (long long s1, long long s2, long long p, long long s) {
    p = m - p;
    if (dkw(s1, p) == 1) return false;
    if (dkw(s2, p) == 1) return false;
    if (dkw(s, p + 1) == 1) return false;
    if (dkw(s, p + 2) == 1) return false;
    return true;
} // s1 p, s2 p, s p - 1, s p - 2

void dfs (long long i, long long s1, long long s2, long long p, long long s) {
    if (p > m) {
        f[i + 1][s][s1] += f[i][s1][s2];
        return;
    }
    dfs(i, s1, s2, p + 1, s);
    if (a[i][p] && inlaw(s1, s2, p, s)) 
        dfs(i, s1, s2, p + 1, s | (1 << (m - p)));
}

int main () {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", S);
        for (long long j = 0; j < (long long)(strlen(S)); j++)
            if (S[j] == 'P') a[i][j + 1] = 1;
            else a[i][j + 1] = 0;
    }
    f[0][0][0] = 1ll;
    for (long long i = 0; i < n; i++)
        for (long long s1 = 0; s1 < (1 << m); s1++)
            for (long long s2 = 0; s2 < (1 << m); s2++)
                dfs(i, s1, s2, 1, 0);
    long long Max = 0;
    for (long long s1 = 0; s1 < (1 << m); s1++)
        for (long long s2 = 0; s2 < (1 << m); s2++)
            Max = max(Max, f[n][s1][s2]);
//  for (long long s1 = 0; s1 < (1 << m); s1++) {
//      for (long long s2 = 0; s2 < (1 << m); s2++)
//          printf("%lld ", f[n][s1][s2]);
//      puts("");
//  }
    printf("%lld", Max);
    return 0;
}