USACO08NOV奶牛混合起来MixedUpCows-洛谷2915

发表于
  • 题意
    $N ( 1 \le N \le 16 ) $头奶牛，每头奶牛有一个权值$S_i ( 1 \le S_i \le 25000 ) $，求有多少排列，满足相邻的两个奶牛权值的差均超过$K ( 1 \le K \le 3400 ) $。
  • Solution
    • $N$范围不大，容易想到可以用状压DP做。
    • 有一个自己不太会的小技巧：DP时计算当前状态对其他状态的贡献，在有些题上很方便，而不是一味的用其他状态计算当前。
    • 设$f[x][i]$代表当前队伍中奶牛的存在情况为$i$，排在最后一个的是$x$时的方案数。
    • 不难发现有$ f[k][i|1<<(k-1)] += f[x][i], k \notin {i} $
    • 最后统计一下答案就行了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const LL maxn = 16 ;
LL n, m, s[maxn], f[maxn+1][1<<maxn] ;
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "LG2915.in", "r", stdin ) ;
    freopen ( "LG2915.out", "w", stdout ) ;
#endif
    LL i, j, k, sit ;
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= n ; i ++ ) Read(s[i]) ;
    sort ( s+1, s+n+1 ) ;
    sit = 1<<n ;
    for ( i = 1 ; i <= n ; i ++ )
        f[i][1<<(i - 1)] = 1 ;
    for ( i = 0 ; i < sit ; i ++ )
        for ( j = 1 ; j <= n ; j ++ )
            if ( i&(1<<(j - 1) ) )
                for ( k = 1 ; k <= n ; k ++ )
                    if ( abs(s[k] - s[j]) > m && !(i&(1<<(k - 1)) ) )
                        f[k][i|(1<<(k - 1))] += f[j][i] ;
    LL ans = 0 ;
    for ( i = 1 ; i <= n ; i ++ )
        ans += f[i][sit- 1] ;
    printf ( "%lld\n", ans ) ;
    return 0 ;
}