HDU-4529 郑厂长系列故事——N骑士问题 状态压缩DP

时间：2022-01-08 22:45:10

题意：给定一个合法的八皇后棋盘，现在给定1-10个骑士，问这些骑士不能够相互攻击的拜访方式有多少种。

分析：一开始想着搜索写，发现该题和八皇后不同，八皇后每一行只能够摆放一个棋子，因此搜索收敛的很快，但是骑士的话就需要对每一个格子分两种情况进行，情况非常的多，搜索肯定是会超时的。状态压缩DP就是另外一个思路的，理论上时间复杂度是8*n*2^24，但是由于限制比较多，也就能够解决了。设dp[i][j][p][q]表示第i-1行压缩后的状态是p，第i行压缩后的状态为q，且之前一共使用了j个骑士的方案数。按照题意递推即可。

#include <cstdio>

#include <cstring>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int LIM = <<;

const int M = ;

int n;

int dp[][M+][LIM][LIM];

// dp[i][j][p][q]表示第i-1行状态为p，第i行状态为q，并且一共使用j个骑士的状态数

int G[M];

int tot[LIM];

char f1[LIM][LIM]; // 相邻两层两个状态之间是否冲突

char f2[LIM][LIM]; // 与上上行两个状态之间是否冲突 

void pre() {

    for (int i = ; i < LIM; ++i) {

        for (int j = ; j < ; ++j) {

            if (i & ( << j)) ++tot[i];

        }

        for (int j = ; j < LIM; ++j) {

            if ((i>>)&j || (j>>)&i) f1[i][j] = ;

            if ((i>>)&j || (j>>)&i) f2[i][j] = ;

        }

    }

}

void solve() {

    int cur = , nxt = ;

    memset(dp, , sizeof (dp));

    dp[cur][][][] = ;

    for (int i = ; i < ; ++i) { // 由dp[i]来推导dp[i+1]

        for (int j = ; j <= n; ++j) {

            for (int p = ; p < LIM; ++p) {

                for (int q = ; q < LIM; ++q) {

                    if (!dp[cur][j][p][q]) continue;

                    for (int z = ; z < LIM; ++z) {

                        if ((z & G[i+]) != z) continue;

                        if (tot[z] + j > n) continue;

                        if (i >=  && f1[q][z]) continue;

                        if (i >=  && f2[p][z]) continue;

                        dp[nxt][tot[z]+j][q][z] += dp[cur][j][p][q];

                    }

                }

            }

        }

        memset(dp[cur], , sizeof (dp[cur]));

        swap(cur, nxt);

    }

    int ret = ;

    for (int i = ; i < LIM; ++i) {

        for (int j = ; j < LIM; ++j) {

            ret += dp[cur][n][i][j];

        }

    }

    printf("%d\n", ret);

}

int main() {

    int T;

    char str[];

    pre();

    scanf("%d", &T);

    while (T--) {

        memset(G, , sizeof (G));

        scanf("%d", &n);

        for (int i = ; i <= ; ++i) {

            scanf("%s", str);

            for (int j = ; j < ; ++j) {

                G[i] <<= ;

                if (str[j] == '.') G[i] |= ;

            }

        }

        solve();

    }

    return ;

}

相关文章