洛谷 P2915 【[USACO08NOV]奶牛混合起来Mixed Up Cows】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 typedef long long llt;
 7 const int maxn=16;
 8 int n,k;
 9 //每只奶牛的高度 
10 int a[maxn];
11 //记忆化数组 
12 llt dp[maxn][1<<maxn];
13 
14 void init() {
15     scanf("%d%d",&n,&k);
16     for (int i=0;i<n;i++)
17         scanf("%d",a+i);
18     //因为可能搜索完答案是0，所以说要初始化成-1 
19     memset(dp,-1,sizeof(dp));
20 }
21 
22 //搜索以x号奶牛为队尾，状态为S时可以有多少种情况 
23 llt dfs(int x, int S) {
24     //如果全部奶牛都能放进来，且构成了一个混乱队形，则有一种情况 
25     if (S==(1<<n)-1) return 1;
26     //记忆化 
27     if (dp[x][S]!=-1) return dp[x][S];
28     llt res=0;
29     for (int i=0;i<n;i++) {
30         //判断是否符合情况 
31         if (S&(1<<i)) continue;
32         if (abs(a[x]-a[i])<=k) continue;
33         //继续搜索 
34         res+=dfs(i,S|(1<<i));
35     }
36     return dp[x][S]=res;
37 }
38 
39 int main() {
40     init();
41     llt ans=0;
42     //每种奶牛都当一次队头 
43     for (int i=0;i<n;i++)
44         ans+=dfs(i,1<<i);
45     printf("%lld\n",ans);
46     return 0;
47 }