洛谷 P2915 [USACO08NOV]Mixed Up Cows G（状压dp）

传送门

---

解题思路

和上一题相似，用dp[i][j]表示当前状态为i，刚刚放的是第j头奶牛的方案数。

其中i的二进制位表示第k位的奶牛到目前为止是否已经选择。

一开始初始化只有一头奶牛时方案数为1，然后枚举状态、上一个位置的奶牛、这一个位置的奶牛转移过来即可。

AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[70000][20],a[25],ans;
int n,kk;
int main()
{
    cin>>n>>kk;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) dp[1<<(i-1)][i]=1;
    for(int i=1;i<=(1<<n)-1;i++){
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1))){
                for(int k=1;k<=n;k++){
                    if(!(i&(1<<(k-1)))) continue;
                    if(abs(a[j]-a[k])<=kk) continue;
                    dp[i][k]+=dp[i-(1<<(k-1))][j];
                } 
            }
        }
    }
    for(int i=1;i<=n;i++) ans+=dp[(1<<n)-1][i];
    cout<<ans;
    return 0;
}