洛谷 P2915 [USACO08NOV]Mixed Up Cows G

Description

P2915 [USACO08NOV]Mixed Up Cows G

Solution

状压(dp)

首先设计状态：(f[i][j]) 表示以 (i) 结尾的状态为 (j) 且符合条件的排列共有多少种。

最终的 (ans = {sum_{i = 1} ^ {n} f[i][(1<<n) - 1]})

再来看转移方程。

当状态(j) 中不包含 (k)，且状态 (j) 中包含 (i)，那么：

(f[i][j | (1 << (k - 1))] += f[k][j])

然后就没别的啦，下面代码中 (i) 和 (j) 是反过来的。

注意要开 (long long)

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 20;
ll n, m;
ll f[N][1 << 17], a[N];

signed main(){
    scanf("%d%d", &n, &m);
    for(ll i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        f[i][1 << (i - 1)] = 1;
    }
    for(ll i = 0; i < (1 << n); i++)
        for(ll j = 1; j <= n; j++)
            for(ll k = 1; k <= n; k++){
                if(!(i & (1 << (j - 1))) && (i | (1 << (k - 1))) == i && abs(a[j] - a[k]) > m)
                    f[j][i | (1 << (j - 1))] += f[k][i];
            }
    ll ans = 0;
    for(ll i = 1; i <= n; i++)
        ans += f[i][(1 << n) - 1];
    printf("%lld
", ans);
    return 0;
}

End