[USACO08NOV]奶牛混合起来

标签： 状态压缩 动态规划

---

题目描述

约翰家有N（4<=N<=16）头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

输入输出格式

输入格式

• Line 1: Two space-separated integers: N and K

• Lines 2: N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i

  输出格式

• Line 1: A single integer that is the number of ways that N cows can be ‘Mixed Up’. The answer is guaranteed to fit in a 64 bit integer.

  输入输出样例

输入样例#1：
4 1
3
4
2
1

输出样例#1：
2

题解

题目中有两个要求：
1.必须将奶牛排成一列。
2.相邻奶牛绝对值不能超过K。
并且总头数很少，因此可以想到把奶牛排列状态压缩起来。
设f[i][j]表示奶牛排列状态为i时末尾为j的奶牛。
转移也就一目了然了。

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

代码

#include<bits/stdc++.h>
#define N 20
#define M (1 << 16)
#define ll long long
using namespace std;

int n, m;
ll a[N], f[M][N], ans = 0;

int main()
{
    scanf("%d%d", &n, &m);
    f[0][0] = 1;
    for(int i = 1; i <= n ; i ++)
    {
        scanf("%lld", &a[i]);
        f[(1 << (i - 1))][i] = 1;
    }
    for(int i = 1; i < (1 << n); i ++)
        for(int j = 1; j <= n; j ++)
            if(i & (1 << (j - 1)))
               for(int k = 1; k <= n; k ++)
                   if(abs(a[j] - a[k]) > m && !(i & (1 << (k - 1))))
                      f[i | (1 << (k - 1))][k] += f[i][j];// printf("f[%d][%d]=%d %d %d", i | (1 << (k - 1)), k, f[i | (1 << (k - 1))][k], i, j), system("pause");
    for(int i = 1; i <= n; i ++)
        ans += f[(1 << n) - 1][i];
    printf("%lld", ans);                  
    return 0;
} 
/*
16 3
89 65 5 78 41 22 33 6 9 10 14 93 22 57 84 101
7 15
9 87 54 63 22 21 85
*/