MnZn 小力分讨 状压求调

RT

#include<bits/stdc++.h>
using namespace std;

int n, m, cnt = 0;
int ss[105], ok[62], numk[62];
int f[105][66][66];

void ycl() {
    for(int s = 0; s <= (1 << m) - 1; s++) {
        if((((s << 1) | (s << 2) | (s >> 1) | (s >> 2)) & s) == 0) {
            ok[++cnt] = s;
            int s1 = s, k = 0;
            while(s1) {
                if(s1 & 1) k++;
                s1 >>= 1; 
            }
            numk[cnt] = k;
        }
    }
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    ycl();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char ch = getchar();
            if(ch == 'P') ss[i] = ss[i] << 1 | 1;
            if(ch == 'H') ss[i] = ss[i] << 1;
        }
        char ch = getchar();
    }

    for(int i = 1; i <= cnt; i++) if(ok[i] & ss[1] == 0) f[1][0][i] = numk[i]; 
    // ycl第一行 
    if(n >= 2) {
        for(int i = 1; i <= cnt; i++) {
            for(int j = 1; j <= cnt; j++) {
                if(!(ok[i] & ok[j]) && !(ok[j] & ss[2]) && !(ok[i] & ss[2])) f[2][i][j] = max(f[2][i][j], f[1][0][i] + numk[j]);
            }
        } 
    }                                           
    // ycl第二行 
    for(int i = 3; i <= n; i++) {
        for(int now = 1; now <= cnt; now++) {
            for(int lst1 = 1; lst1 <= cnt; lst1++) {
                for(int lst2 = 1; lst2 <= cnt; lst2++) {
                    if(!(ok[lst2] & ok[lst1]) && !(ok[lst1] & ok[now]) && !(ok[lst2] & ok[now]) && !(ok[lst2] & ss[i]) && !(ok[lst1] & ss[i]) && !(ok[now] & ss[i])) f[i][lst1][now] = max(f[i][lst1][now], f[i - 1][lst2][lst1] + numk[now]);
                }
            }
        }
    }
    //dp
    int mx = -1;
    for(int lst1 = 1; lst1 <= cnt; lst1++) {
        for(int lst2 = 1; lst2 <= cnt; lst2++) {
            mx = max(mx, f[n][lst2][lst1]);
        }
    }
    printf("%d", mx);
}