题解 - [Luogu P2915] [USACO08NOV] 奶牛混合起来 Mixed Up Cows

发表于 更新于 分类于 ， 本文字数： 578 阅读时长 ≈ 2 分钟

题目链接

原始题面

题目描述

Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有 \(N\) 头奶牛，第 \(i\) 头奶牛的编号是 \(S_i\), 每头奶牛的编号都是唯一的

这些奶牛最近在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍

在一只混乱的队伍中，相邻奶牛的编号之差均超过 \(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

1
2
3
4
5
4 1
3
4
2
1

输出样例 #1

1
2

说明 / 提示

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

解题思路

令 \(f(n,m)\) 表示以 \(m\) 结尾，状态为 \(n\) 时的方案数。若 \(n\ \mathrm{And}\ 2^{i-1} \neq 0\), 则说明 \(i\) 在队伍中

  • 初始状态

    \[ f(2^{i-1},i)=1 \]

  • 状态转移方程

    \[ f(i,j)=\displaystyle\sum_{k} f(i\oplus\ 2^{k-1},k) \]

    其中 \(1\leqslant k\leqslant n,\ i\ \mathrm{And}\ 2^{k-1}=0\)

  • 最终结果:

    \[ \sum_{i=1}^n f(2^n-1,i) \]

时间复杂度

\(O(n^2 2^n)\)

代码参考

Show code

Luogu_P2915view raw
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#define _rep(i, l, r) for (auto i = (l); i < (r); ++i)
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
int p, p3 = -1;
int getc() {
  return p1 == p2 &&
             (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
           EOF :
           *p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  int f = 0;
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getc();
  }
  if (f) x = -x;
  read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = hh;
  print(oth...);
}
template <typename T>
void print_h(T x, char h) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = h;
}
void putchar(char a) { buf2[++p3] = a; }
}  // namespace FastIO
using FastIO::print;
using FastIO::print_h;
using FastIO::read;
const int M = 1 << 16;
const int N = 17;
i64 f[M][N], s[N], n, delta;
int main() {
  read(n, delta);
  _rep(i, 0, n) read(s[i]);
  _rep(i, 0, n) f[1 << i][i] = 1;
  _rep(i, 0, 1 << n) {
    _rep(j, 0, n) {
      if (!(i & (1 << j))) continue;
      _rep(k, 0, n) {
        if (i & (1 << k)) continue;
        if (s[j] - s[k] > delta || s[k] - s[j] > delta)
          f[i | (1 << k)][k] += f[i][j];
      }
    }
  }
  i64 ans = 0;
  _rep(i, 0, n) ans += f[(1 << n) - 1][i];
  print(ans);
ex:
  FastIO::flush();
  return 0;
}