[COGS 1517] 放国王

题目描述

原题地址：COGS

思路

对于此题，先考虑一个弱化版的题目：

• 在$n\times n$的棋盘上放国王，有多少种方法？

我们可以预处理出所有状态，然后DP的时候判断，如果不冲突，那么转移。

对于$k$个国王的限制，需要在状态上加一维。

状态设计

设$f(i,j,l)$表示第$i$行放了$j$个国王，状态为$l$时的方案数。

则有: $$ f(i,j,l)=f(i-1,m,a) $$ 当且仅当$a$可以转移到$l$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
int s[1 << 10], num[1 << 10];
ll ans, f[12][110][(1 << 10) + 10];
int main()
{
    freopen("placeking.in", "r", stdin);
    freopen("placeking.out", "w", stdout);
    cin >> n >> k;
    //=============预处理==================
    int st = 0;
    for (int i = 0; i < (1 << n); ++i)
    {
        if (i & (i << 1)) // 与上一行冲突（由于每行都相同，即与自己冲突）
            continue;
        int t = i;
        while (t)
        {
            num[st] += (t & 1);
            t >>= 1;
        }
        s[st++] = i;
    }
    for (int i = 0; i < st; ++i)
        if (num[i] <= k)
            ++f[1][num[i]][i];
    //=====================================
    for (int i = 2; i < n; ++i)          // 枚举行
        for (int j = 0; j <= k; ++j)     // 枚举棋子
            for (int l = 0; l < st; ++l) // 枚举当前行状态
            {
                int m = j - num[l];
                for (int o = 0; o < st; ++o) //枚举上一行状态
                {
                    if (num[o] > m || s[l] & s[o] || (s[l] << 1) & s[o] || s[l] & (s[o] << 1)) // 不符合转移条件
                        continue;
                    f[i][j][l] += f[i - 1][m][o]; //转移
                }
            }
    // 最后一行的处理
    for (int i = 0; i < st; ++i)
    {
        int m = k - num[i];
        for (int j = 0; j < st; ++j)
        {
            if (num[j] > m || s[i] & s[j] || (s[i] << 1) & s[j] || s[i] & (s[j] << 1))
                continue;
            f[n][k][i] += f[n - 1][m][j];
        }
        ans += f[n][k][i];
    }
    cout << ans << endl;
}