1 条题解

  • 0
    @ 2025-10-8 17:03:18
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll a[17], d[17], f[17][1 << 16];
    // f[i][s]表示状态s下以i结尾的方案数
    int main()
    {
        ll n, K; scanf("%lld%lld", &n, &K);
        for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
        
        d[1] = 1; for (ll i = 2; i <= n; i++) d[i] = d[i - 1] * 2;
    
        for (ll i = 1; i <= n; i++) f[i][d[i]] = 1; // 初始化
    
        for (ll s = 1; s < (1 << n); s++) // 枚举每个状态
        {
            for (ll i = 1; i <= n; i++) if (s & d[i]) // 枚举末尾可能的奶牛
            {
                for (ll j = 1; j <= n; j++) if (!(s & d[j])) // 枚举接下来要放的奶牛
                {
                    if (abs(a[j] - a[i]) > K) f[j][s | d[j]] += f[i][s]; // 状态转移
                }
            }
        }
        ll ans = 0; for (ll i = 1; i <= n; i++) ans += f[i][(1 << n) - 1]; // 统计答案
        printf("%lld", ans); // 输出
        return 0;
    }
    
    • 1

    *【状态压缩DP】[USACO08NOV] Mixed Up Cows G

    信息

    ID
    2884
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    30
    已通过
    18
    上传者