思路

这道题观察数据范围和题干，可以得知这是一道状压dp的题目。我们先来设计状态：在本题中，可以类比互不侵犯的那一题（互不侵犯题解），设计成当前状态和上一状态相关的元素。可以想出，dp[当前牛的存在情况][当前加入的牛的编号] += dp[上一次加入后的状态][上一次加入的牛的编号];

基本上完成了思考，现在我们先来搞定预处理。我们把只有cowId在队列里的方案数初始化为1。

for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;

之后我们就可以进行dp了。详细见代码：

for (int lastState = 0; lastState < (1 << n); lastState++)
    for (int lastCow = 0; lastCow < n; lastCow++)
        if (lastState & (1 << lastCow))
            for (int nowCow = 0; nowCow < n; nowCow++)
                if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                    nowState = lastState | (1 << nowCow),
                    dp[nowState][nowCow] += dp[lastState][lastCow];

最后方案数叠加，在满员的状态下枚举最后一头牛的id。

ll ans = 0;
for (int i = 0; i < n; i++)
    ans += dp[(1 << n) - 1][i];
cout << ans;

代码

// P2915.cpp
#include <iostream>
#include <cmath>
using namespace std;

#define ll unsigned long long
const int maxn = 16;
ll dp[1 << maxn][maxn];
int n, k, nowState;
int seq[maxn];

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> seq[i];
    for (int cowId = 0; cowId < n; cowId++)
        dp[1 << cowId][cowId] = 1;
    for (int lastState = 0; lastState < (1 << n); lastState++)
        for (int lastCow = 0; lastCow < n; lastCow++)
            if (lastState & (1 << lastCow))
                for (int nowCow = 0; nowCow < n; nowCow++)
                    if (!(lastState & (1 << nowCow)) && abs(seq[nowCow] - seq[lastCow]) > k)
                        nowState = lastState | (1 << nowCow),
                        dp[nowState][nowCow] += dp[lastState][lastCow];
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans;
    return 0;
}