求教为什么RE 感谢大佬
查看原帖
求教为什么RE 感谢大佬
1189972
selinar楼主2024/3/25 23:18
#include <iostream>
#include <algorithm>
using namespace std;
int num;
long long status[10][101][2000], cnt[4000], check[4000], ans = 0;

void dp(int N, int K)
{
    for (int s = 0; s < (1 << N); s++) // 1右移n位 所以s可以用来表示一行n列的棋盘放king的所有可能
    {
        int tmp = 0, s_tmp = s;
        while (s)
        {
            if (s & 1)
                tmp++;
            s = s >> 1;
        }
        cnt[s_tmp] = tmp; // 该种可能的王个数
        if ((((s_tmp << 1) | (s_tmp >> 1)) & s_tmp) == 0)
        {
            check[++num] = s_tmp; // 合法
        }
    }
    status[0][0][0] = 1;
    for (int i = 1; i <= N; i++)
    {

        for (int t = 1; t <= num; t++)
        {
            int s1 = check[t];
            for (int h = 1; h <= num; h++)
            {
                int s2 = check[h];
                for (int j = 1; j <= K; j++)
                {
                    if (j - cnt[s1] > 0 && ((s2 | (s2 << 1) | (s2 >> 1)) & s1) == 0)
                    {
                        status[i][j][s1] += status[i - 1][j - cnt[s1]][s2];
                    }
                }
            }
        }
    }

    for (int i = 1; i <= num; i++)
    {
        ans += status[N][K][check[i]];
    }
}
int main()
{
    int N, K;
    cin >> N >> K;
    dp(N, K);

    cout << ans << endl;
    return 0;
}
2024/3/25 23:18
加载中...