一道经典的状压
开始没有想出来,但看了培训后,按照$dfs$的思路先想了一遍
假设我们要$dfs$,那我们要知道哪些牛用了,当前是哪头牛
所以状压的状态也就出来了
令$f[i][j]$表示$i$状态,当前在$j$号牛的方案数
有$$f[i][j] = sum_{kin (i-left { j ight })} f[i-left { j ight }][k]$$
!!初始化!!
有$$f[left { i ight }][i] = 1$$
上代码
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #define ll long long 6 using namespace std; 7 8 template <typename T> void in(T &x) { 9 x = 0; T f = 1; char ch = getchar(); 10 while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} 11 while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();} 12 x *= f; 13 } 14 15 template <typename T> void out(T x) { 16 if(x < 0) x = -x , putchar('-'); 17 if(x > 9) out(x/10); 18 putchar(x%10 + 48); 19 } 20 //------------------------------------------------------- 21 22 const int N = 18; 23 24 int n,m,s[N]; 25 ll f[1<<N][N]; 26 27 int main() { 28 int i,j,k; 29 in(n); in(m); 30 for(i = 1;i <= n; ++i) in(s[i]),f[1<<(i-1)][i] = 1;//debug 1<<(i-1) -> 0 31 for(i = 0;i < (1<<n); ++i) { 32 for(j = 1;j <= n; ++j) { 33 if(!(i&(1<<(j-1)))) continue; 34 for(k = 1;k <= n; ++k) { 35 if(!(i&(1<<(k-1))) || k == j || abs(s[j]-s[k]) <= m) continue; 36 f[i][j] += f[i^(1<<(j-1))][k]; 37 } 38 } 39 } 40 ll ans = 0; 41 for(i = 1;i <= n; ++i) ans += f[(1<<n)-1][i]; 42 out(ans); 43 return 0; 44 }