[省选联考 2021 A/B 卷] 滚榜
算法标签：状压 DP，差分，费用提前计算。
题目描述
给定 \(n\) 个非负整数 \(a_1, a_2, \dots, a_n\)，定义 \(d_i\) 表示以 \(a_i\) 为第一关键字降序排序，以 \(i\) 为第二关键字升序排序后的下标。现有 \(n\) 个非负整数 \(b_1, b_2, \dots, b_n\)，满足 \(\sum_{i = 1}^{n} b_i = m\)，且满足以 \(b_i\) 不降的顺序，依次将 \(a_i\) 变成 \(a_i + b_i\)，更新 \(d_i\) 后，\(d_i\) 均为 \(1\)。求最终有多少种不同的 \(d\) 数组。
数据范围：\(1 \le n \le 13\)，\(1 \le m \le 500\)，\(0 \le a_i \le {10}^4\)。
题解
注意到这个每次 \(d_i = 1\) 的限制很强，所以首先分析它的性质。
对于一个排列 \(p\)，表示选择 \(b_i\) 的顺序为 \(\{ p_1, p_2, p_3 \dots p_n\}\)，那么 \(\forall i \in [1,n]\)，都有 \(d_{p_i} = n - i + 1\)，答案就等价于求 \(p\) 的种类数。
我们以 \(p\) 的顺序，每次贪心地选取最小的 \(b_i\)，那么 \(p\) 符合条件等价于 \(\sum\limits_{i = 1}^n b_i \le m\)，形式化地讲，我们定义：
\[f(i, j) = \max(a_{i} - a_{j} + [i < j], \, 0) \]那么容易写出 \(b_i\) 的递推式：
\[b_{p_{i}} = b_{p_{i -1}} + f(p_{i - 1}, p_i) \]通过 \(f(i,j)\) 函数，让我们可以保证 \(b_{p_i}\) 单调不降，即 \(b_{p_{i-1}} \le b_{p_i}\)，还可以保证进行到 \(p_i\) 时都让 \(d_{p_i} = 1\)，所以我们能在 \(\mathcal{O}(n)\) 的时间复杂度内判断一个 \(p\) 的合法性。
至此，我们已经有了一个 \(\mathcal{O}(n! \times n)\) 的算法。
考虑状压 dp，记 \(t = |S|\)，容易设计出朴素状态 \(g_{S, i, j, k}\)，表示目前的 \(\{ p_1, p_2, \dots p_t\}\) 的集合为 \(S\)，且 \(p_t = i\)，\(b_i = j\)，\(\sum\limits_{x \in S} b_x = k\)，则直接转移的复杂度为 \(\mathcal{O}(2^nn^2m^2)\)，无法通过。
由于现在的限制只剩下 \(\sum\limits_{i = 1}^n b_i \le m\) 未完全处理完。通过前面提到 \(b\) 数组的性质，\(\sum\limits_{x \in S} b_x\) 是完全可以利用 \(b\) 数组的差分数组，即 \(f(i, j)\) 快速计算的，因此 \(j\) 这一维可以删去，容易写出新的转移方程：
\[g_{S,i,k} = \sum_{j \in S, j \ne i} g_{S- \{i \}, j, k - f(j, i)} \]注意 dp 的初值，时间复杂度为 \(\mathcal{O}(2^nn^2m)\)。
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define MULT_TEST 0
using namespace std;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 15, R = (1 << 13) + 5, M = 505;
int dp[R][N][M], a[N];
inline int read() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
w = (w << 1) + (w << 3) + ch - 48;
ch = getchar();
}
return w * f;
}
inline void Solve() {
int n, m, mx = 0;
n = read(); m = read();
for (int i = 0; i < n; i++) {
a[i] = read();
if (a[i] > a[mx]) mx = i;
}
for (int i = 0; i < n; i++) {
int r = max(a[mx] - a[i] + (i > mx), 0ll);
dp[1 << i][i][r * n] = 1;
}
for (int S = 1; S < (1 << n); S++) {
int c = __builtin_popcount(S);
if (c == 1) continue;
for (int i = 0; i < n; i++) {
if (!((S >> i) & 1)) continue;
for (int j = 0; j < n; j++) {
if (i == j || !((S >> j) & 1)) continue;
int r = max(a[j] - a[i] + (i > j), 0ll) * (n - c + 1);
for (int k = r; k <= m; k++) dp[S][i][k] += dp[S ^ (1 << i)][j][k - r];
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j <= m; j++)
ans += dp[(1 << n) - 1][i][j];
printf("%lld\n", ans);
}
signed main() {
int T = 1;
#if MULT_TEST
T = read();
#endif
while (T--) Solve();
return 0;
}