题目
题目描述
混乱的奶牛 [Don Piele, 2007] Farmer John的 N(4 <= N <= 16) 头奶牛中的每一头都有一个唯一的编号 \(S_i (1 <= S_i <= 25,000)\). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支”混乱”的队伍非常反感. 如果一个队伍里任意两头相邻的奶牛的编号相差超过K (1 <= K <= 3400), 它就被称为是混乱的. 比如说，当N = 6, K = 1时, 1, 3, 5, 2, 6, 4 就是一支”混乱”的队伍, 但是 1, 3, 6, 5, 2, 4 不是(因为5和6只相差1). 那么, 有多少种能够使奶牛排成”混乱”的队伍的方案呢?
输入描述
第 1 行: 用空格隔开的两个整数N和K* 第 2..N+1 行: 第i+1行包含了一个用来表示第i头奶牛的编号的整数: \(S_i\)
输出描述
第 1 行: 只有一个整数, 表示有多少种能够使奶牛排成”混乱”的队伍的方案. 答案保证是 一个在64位范围内的整数.
示例1
输入
4 1
3
4
2
1
输出
2
题解
知识点：状压dp。
经典TPS，不过更新答案时要求绝对值大于 \(K\)。
时间复杂度 \(O(n^22^n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[20];
ll dp[(1 << 16) + 7][20];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) dp[1 << (i - 1)][i] = 1;
for (int i = 0;i < (1 << n);i++) {
for (int j = 1;j <= n;j++) {
if (!(i & (1 << (j - 1)))) continue;
for (int k = 1;k <= n;k++) {
if (j != k && !(i & (1 << (k - 1)))) continue;
if (abs(a[j] - a[k]) > q) dp[i][j] += dp[i ^ (1 << (j - 1))][k];
}
}
}
ll ans = 0;
for (int i = 1;i <= n;i++) ans += dp[(1 << n) - 1][i];
cout << ans << '\n';
return 0;
}