Luogu P2915 [USACO08NOV]Mixed Up Cows G

题目描述

https://www.luogu.com.cn/problem/P2915

状压dp入门题

Solution

我们只需要在状态中存储已经选的数和最后一个选的数

所以我们令f[s][i]表示已经选的数的集合为s，最后一个选的数是i

转移时枚举下一个数即可，时间复杂度为 $O(2^n n^2)$

#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 17
#define ll long long 
using namespace std;

int n, a[maxn], m;

ll f[1 << maxn][maxn]; 

int main() { 
    cin >> n >> m; int M = (1 << n) - 1; 
    for (int i = 1; i <= n; ++i) cin >> a[i], f[1 << i - 1][i] = 1; 
    for (int S = 1; S <= M; ++S)
        for (int i = 1; i <= n; ++i) {
            if (!(S >> i - 1 & 1)) continue;
            for (int j = 1; j <= n; ++j) {
                if ((S >> j - 1 & 1) || abs(a[j] - a[i]) <= m) continue;
                f[S | 1 << j - 1][j] += f[S][i];
            }
        }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += f[M][i];
    cout << ans << endl; 
}